[leetcode] 1090. Largest Values From Labels

[leetcode] 1090. Largest values From labels

Description

We have a set of items: the i-th item has value values[i] and label labels[i].

Then, we choose a subset S of these items, such that:

|S| <= num_wantedFor every label L, the number of items in S with label L is <= use_limit.Return the largest possible sum of the subset S.

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1Output: 9Explanation: The subset chosen is the first, third, and fifth item.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2Output: 12Explanation: The subset chosen is the first, second, and third item.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1Output: 16Explanation: The subset chosen is the first and fourth item.

Example 4:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2Output: 24Explanation: The subset chosen is the first, second, and fourth item.

Note:

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

分析

题目的意思是：给定values和labels，然后给出限制条件num_wanted和use_limit,num_wanted限制的是values的数量，use_limit限制的是labels的数量。

我参考了一下别人的思路，对values，labels进行从大到小排序，然后遍历，用freq记录遍历过的label的频率，如果不超过use_limit，则可以更新res值，num_wanted减去1，直到num_wanted减少为0为止。

这样就能达到目的了

代码

class Solution: def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int: res=0 freq=defaultdict(int) for value,label in sorted(zip(values,labels),reverse=True): if(freq[label]

参考文献

​​[Python3] greedy O(NlogN)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。