पायथन में लेबल से सबसे बड़े मान

मान लीजिए हमारे पास वस्तुओं का एक समूह है: i-वीं वस्तु का मान values[i] और लेबल labels[i] है। फिर, हम इन वस्तुओं का एक सबसेट S लेंगे, जैसे कि -

• |S| <= num_wanted
• प्रत्येक लेबल L के लिए, S में लेबल L वाली वस्तुओं की संख्या <= use_limit

हमें सबसेट S का सबसे बड़ा संभव योग ढूंढना है।

उदाहरण के लिए, यदि इनपुट values = [5,4,3,2,1] और labels [1,1,2,2,3] हैं, num_wanted = 3, use_limit = 1, तो आउटपुट 9 होगा। ऐसा इसलिए है क्योंकि सबसेट में पहली, तीसरी और पांचवीं वस्तु चुनी गई है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• v नामक एक सरणी बनाएं
• i के लिए 0 से values की लंबाई तक की रेंज में
  • [values[i], labels[i]] को v में डालें
• v सरणी को क्रमबद्ध करें
• ans := 0, use := खाली मैप, और i := 0
• जब num_wanted और i < v की लंबाई
  • यदि v[i, 1] use मैप में मौजूद नहीं है
    • num_wanted को 1 से घटाएं
    • ans := ans + v[i, 0]
    • use[v[i, 1]] := 1
  • अन्यथा use[v[i, 1]] < use_limit
    • num_wanted को 1 से घटाएं
    • ans := ans + v[i, 0]
    • use[v[i, 1]] को 1 से बढ़ाएं
  • i को 1 से बढ़ाएं
• ans लौटाएं

उदाहरण

class Solution(object):
    def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
        v = []
        for i in range(len(values)):
            v.append([values[i], labels[i]])
        v = sorted(v, key=lambda v: v[0], reverse=True)
        ans = 0
        use = {}
        i = 0
        while num_wanted and i < len(v):
            if v[i][1] not in use:
                num_wanted -= 1
                ans += v[i][0]
                use[v[i][1]] = 1
            elif use[v[i][1]] < use_limit:
                num_wanted -= 1
                ans += v[i][0]
                use[v[i][1]] += 1
            i += 1
        return ans

ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1], [1,1,2,2,3], 3, 1))

इनपुट

[5,4,3,2,1] [1,1,2,2,3] 3 1

आउटपुट

9