LEETCODE 1090. Largest Values From Labels 解题思路分析

题目大意：

受标签影响的最大值

我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。

我们从这些项中选出一个子集 S，这样一来：

1. |S| <= num_wanted
2. 对于任意的标签 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 。在这个条件下，求出取出数字总和最大的解。

题目本身其实难度不是很大，大概分三步即可算出答案。

1. 做一个map，key是label，value是List，用于记录每种label都包含那些数字。并分别将这些数字List按照从大到小排序。
2. 分别取出每个List中前 use_limit 大的数字，统一存放到一个新的List中，并对此List进行从大到小排序。
3. 从第二步获得的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-解题思路分析/