受标签影响的最大值

题目

---

我们有一个 n 项的集合。给出两个整数数组 values 和 labels，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

从 n 个元素中选择一个子集 s :

• 子集 s 的大小，小于或等于 numWanted 。
• s 中 最多 有相同标签的 useLimit 项。

一个子集的 分数 是该子集的值之和。

返回子集 s 的 最大分数 。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出：16
解释：选出的子集是第一项和第四项。

提示：

• n == values.length == labels.length
• 1 <= n <= 2 * 104
• 0 <= values[i], labels[i] <= 2 * 104
• 1 <= numWanted, useLimit <= n

分析题目

这道题读懂题目，会发现其实并不难，属于中等题中的简单题，但问题是题目写的让人难以理解，不明所以，所以分析题目是这道题的关键。

1. 现在有等长的两个数组：values 和 labels， 长度记作 n
2. 同时第 i 项的 value 与 label 正好对应的是：values[i] 与 lables[i]
3. 还会给出两个整数参数 numWanted 和 useLimit
4. numWanted 代表子集的个数， useLimit 代表子集 label 允许重复的个数
5. 要求从 n 个元素中，选择一个子集 s

子集 s 的条件必须满足一下规则：

1. 子集 s 的元素个数，即集合长度，小于或等于 numWanted
2. 子集 s 中最多有 useLimit 个相同 label

返回这满足子集条件的分数，即子集数组中每一个元素累加之和。

即， 由于 label 与 values 是对应关系， label 又存在重复项，所以我们需要从 label 中选择 useLimit 个最大值即可。

方法1：哈希表+排序

---

思路

根据题目分析，我们已经知道，只需要获取每个 label 的 useLimit 最大值即可，所以我们可以对 values 进行降序排序，排序完成后依次取值进行判断是否符合规则，同时使用 哈希表 记录每一种标签已经选择的个数即。

• 我们直接对 numWanted 进行自减，当 numWanted == 0 时，终止循环。
• 当 map 中的 label 个数等于 useLimit 时，跳过当前元素。

关于 values 与 labels 排序

因为 values 和 labels 是互相关联的两个数组，直接使用系统排序算法对两个数组进行排序会比较困难，需要手写实现，所以这里单独维护一个有序列表，当 values 与 labels 取值时，直接取 values[id[i]] 即可。

具体实现

Java 实现

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;s
        // 因为 values 和 labels 是互相关联的两个数组
        // 系统排序算法直接使用会比较困难，需要手写
        // 所以这里单独维护一个有序列表
        int[] id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        Arrays.sort(id, (a, b) -> values[b] - values[a]);

        int sum = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < n && numWanted > 0; i++){
            int current = labels[id[i]];
            int cnt = map.getOrDefault(current, 0);
            if(cnt >= useLimit) continue;
            map.put(current, ++cnt);
            sum += values[id[i]];
            numWanted--;
        }
        return sum;
    }
}

JavaScript 实现

var largestValsFromLabels = function(values, labels, numWanted, useLimit) {
    const n = values.length;
    const id = [];
    for (let i = 0; i < n; i++) {
        id[i] = i;
    }
    id.sort((a, b) => values[b] - values[a]);

    let sum = 0;
    const map = new Map();
    for(let i = 0; i < n && numWanted > 0; i++){
        let current = labels[id[i]];
        let cnt = map.get(current) || 0;
        if(cnt >= useLimit) continue;
        map.set(current, ++cnt);
        sum += values[id[i]];
        numWanted--;
    }
    return sum;
};

复杂度分析

• 时间复杂度： $O(n\ log_n)$ 排序算法时间复杂度为 $O(n\ log_n)$，后续遍历时间复杂度为 $O(n)$
• 空间复杂度： $O(n)$ 数组id 与 map 的空间复杂度都为 $O(n)$