题目链接

英文链接：https://leetcode.com/problems/largest-values-from-labels/

中文链接：https://leetcode-cn.com/problems/largest-values-from-labels/

题目详述

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

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

|S| <= num_wanted
对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。

返回子集 S 的最大可能的和。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

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

示例 4：

1
2
3

输入：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

题目详解

按照 values 进行贪心。
按照 values 从大到小排序，如果所用标签次数不超过 use_limit，说明可以选用；否则不能选用。为了记录标签出现次数，需要一个哈希表。

public class LeetCode_01090 {

    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        class Data implements Comparable<Data> {
            int value, label;

            public Data(int value, int label) {
                this.value = value;
                this.label = label;
            }

            @Override
            public int compareTo(Data o) {
                return Integer.compare(o.value, this.value);
            }
        }
        int n = values.length;
        Data[] ds = new Data[n];
        for (int i = 0; i < n; ++i) {
            ds[i] = new Data(values[i], labels[i]);
        }
        Arrays.sort(ds);
        int[] map = new int[20001];
        int res = 0;
        for (int i = 0; i < n && num_wanted != 0; ++i) {
            if (++map[ds[i].label] <= use_limit) {
                res += ds[i].value;
                --num_wanted;
            }
        }
        return res;
    }
}