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-解题思路分析/
此条目发表在leetcode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

邮箱地址不会被公开。