前言

Weekly Contest 141的 受标签影响的最大值：

我们有一个项的集合，其中第 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. 1 <= values.length == labels.length <= 20000
  2. 0 <= values[i], labels[i] <= 20000
  3. 1 <= num_wanted, use_limit <= values.length

解题思路

本题题目可能会有点难以理解，可用把题目中的项看做带有值的标签。而labels就是标签列表，values就是标签列表对应的标签值列表。

简单点说，标签与标签值的关系为多对多，一个标签可以有多个标签值，而一个相同的值可以多个标签都使用。

而题目的意思就是在所有项中选取num_wanted个元素，但是选取的元素如果存在标签一致的情况，只能存在use_limit个相同标签的项。找出满足上述条件的子集，且该子集的项的标签值之和最大，并返回该最大值。

下面我以示例4作为例子，讲解一下我的解题思路：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2输出：24解释：选出的子集是第一项，第二项和第四项。

  1. 将values和labels转化为以values为key，每个key对应多个label的结构，同时以key从大到小进行排序。内容如下所示

    9 : [0]8 : [0,0]7 : [1]6 : [1]

  2. 依次遍历第1步中的数据并进行处理，处理步骤如下：

    1. 遍历key对应的label列表
    2. 如果该label使用次数小于use_limit，则将将最大值加上对应的key，同时num_wanted自减
    3. 每轮循环都要判断num_wanted是否为0

实现代码

    /**     * 1090. 受标签影响的最大值     * @param values 标签值列表     * @param labels 标签名列表     * @param num_wanted 期待的标签个数     * @param use_limit 每个标签可重复的次数     * @return     */    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {        // value和label的映射，需要注意使用的是入参values作为key倒序（从大到小）存储        Map<Integer, List<Integer>> valueLabelMap = new TreeMap<>(Comparator.reverseOrder());        // 每个label的出现次数        Map<Integer,Integer> occurTimes = new HashMap<>();        // 最大值        int result = 0;        for(int i=0;i<labels.length;i++){ // 转成value和label的映射            if(valueLabelMap.containsKey(values[i])){                valueLabelMap.get(values[i]).add(labels[i]);            }else{                List<Integer> list=new ArrayList<>();                list.add(labels[i]);                valueLabelMap.put(values[i],list);            }        }        Iterator<Map.Entry<Integer,List<Integer>>> it=valueLabelMap.entrySet().iterator();        while (it.hasNext()){ // 遍历TreeMap            Map.Entry<Integer,List<Integer>> entry = it.next();            // 对应的值            Integer value = entry.getKey();            List<Integer> labelList = entry.getValue();            labelList.sort(Comparator.comparing(Integer::intValue));            for(int i=0;i<labelList.size();i++){ // 遍历label列表                Integer label=labelList.get(i);                if(occurTimes.containsKey(label)){ // label是否被使用过                    if(occurTimes.get(label)<use_limit){ // 是否超出使用上限                        result+=value;                        occurTimes.put(label,occurTimes.get(label)+1);                        --num_wanted; // 减少可用个数                    }                }else{                    occurTimes.put(label,1);                    result+=value;                    --num_wanted; // 减少可用个数                }                if(num_wanted==0){ // 可用个数为0，中断循环                    break;                }            }            if(num_wanted==0){                break;            }        }        return result;    }