Leetcode 1090.受标签影响的最大值

1 题目描述（Leetcode题目链接）

  我们有一个项的集合，其中第 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 解释：选出的子集是第一项，第三项和第五项。 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2 输出：12 解释：选出的子集是第一项，第二项和第三项。

提示：

1 <= values.length == labels.length <= 200000 <= values[i], labels[i] <= 200001 <= num_wanted, use_limit <= values.length

2 题解

  对values逆序排序，用一个字典记录每种标签出现的次数，尽可能选择值大的。

class Solution: def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int: res = 0 arr = sorted(list(zip(values, labels)), key=lambda x:x[0], reverse=True) lab = collections.defaultdict(int) for val, label in arr: if lab[label] < use_limit: res += val lab[label] += 1 num_wanted -= 1 if num_wanted == 0: break return res