题目大意：
受标签影响的最大值
我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。
我们从这些项中选出一个子集 S，这样一来：
- |S| <= num_wanted
- 对于任意的标签
L，子集S中标签为L的项的数目总满足<= use_limit。
返回子集 S 的最大可能的 和。
示例 1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。
示例 2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。
示例 3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。
示例 4：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。
提示：
1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1090
解题思路分析：
这道题读了几遍才搞清楚题目的意思。不知道本题差评数比较多的原因是否和题目描述混乱有关。
本题的大意是，有一个 values 数组和一个labels数组， 其长度相同，对于 values 中的每个值，都有一个相对应（相同下标）的label值存储在 labels数组中，不同的value的label值可能会相同。题目要求在 values 数组中最多取出 num_wanted 个数字，并且相同label的数字个数不能超过 use_limit 。在这个条件下，求出取出数字总和最大的解。
题目本身其实难度不是很大，大概分三步即可算出答案。
- 做一个map，key是label，value是List，用于记录每种label都包含那些数字。并分别将这些数字List按照从大到小排序。
- 分别取出每个List中前 use_limit 大的数字，统一存放到一个新的List中，并对此List进行从大到小排序。
- 从第二步获得的List中取出前 num_wanted 个数字并求和即为结果。
看下完整代码：（由于思路并不复杂，代码中就不写注释了）
public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
List[] map = new List[20001];
for(int i=0;i<values.length;i++){
List<Integer> valueList= map[labels[i]];
if(valueList==null){
valueList = new ArrayList<>();
}
valueList.add(values[i]);
map[labels[i]] = valueList;
}
List<Integer> list = new ArrayList<>();
for(int key=0;key<map.length;key++){
List<Integer> valueList= map[key];
if(valueList==null){
continue;
}
Collections.sort(valueList, Comparator.reverseOrder());
for(int i=0;i<use_limit&&i<valueList.size();i++){
list.add(valueList.get(i));
}
}
Collections.sort(list, Comparator.reverseOrder());
int res=0;
for(int i=0;i<num_wanted&&i<list.size();i++){
res+=list.get(i);
}
return res;
} 本解法用时18ms。
Runtime: 18 ms, faster than 89.42% of Java online submissions for Largest Values From Labels.
Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Largest Values From Labels.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1090-largest-values-from-labels-解题思路分析/