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

英文原文

There is a set of n items. You are given two integer arrays values and labels where the value and the label of the ith element are values[i] and labels[i] respectively. You are also given two integers numWanted and useLimit.

Choose a subset s of the n elements such that:

• The size of the subset s is less than or equal to numWanted.
• There are at most useLimit items with the same label in s.

The score of a subset is the sum of the values in the subset.

Return the maximum score of a subset s.

 

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth items.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third items.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
Output: 16
Explanation: The subset chosen is the first and fourth items.

Example 4:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth items.

 

Constraints:

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

中文题目

我们有一个项的集合，其中第 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

通过代码

高赞题解

思路

items[i][0]存value，items[i][1]存label。
根据value降序排序，每次取当前最大的value，若能添加到最终结果中则添加。

Java代码

[-HashMap]
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        int len = values.length;
        int[][] items = new int[len][2];
        for (int i = 0; i < len; ++i) {
            items[i][0] = values[i];
            items[i][1] = labels[i];
        }
        Arrays.sort(items, Comparator.comparingInt(i -> -i[0]));
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int[] item : items) {
            int label_count = map.getOrDefault(item[1], 0);
            if (label_count < use_limit) {
                res += item[0];
                if (--num_wanted == 0)
                    break;
                map.put(item[1], label_count + 1);
            }
        }
        return res;
    }
}

[-数组]
//既然题目说了label的值的范围是[0, 20000]，那就将HashMap改为数组，速度更快。
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        int len = values.length;
        int[][] items = new int[len][2];
        for (int i = 0; i < len; ++i) {
            items[i][0] = values[i];
            items[i][1] = labels[i];
        }
        Arrays.sort(items, Comparator.comparingInt(i -> -i[0]));
        int[] label_count = new int[20001];
        int res = 0;
        for (int[] item : items) {
            if (label_count[item[1]] < use_limit) {
                res += item[0];
                if (--num_wanted == 0)
                    break;
                ++label_count[item[1]];
            }
        }
        return res;
    }
}

C++代码

[-unordered_map]
class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        size_t len = values.size();
        vector<vector<int>> items;
        for (size_t i = 0; i < len; ++i)
            items.push_back({values[i], labels[i]});
        
        sort(items.begin(), items.end(), [](vector<int>& a, vector<int>& b) {return b[0] < a[0];});
        unordered_map<int, size_t> item_map;
        int res = 0;
        for (const auto& item : items) {
            if (item_map[item[1]] < use_limit) {
                res += item[0];
                if (--num_wanted == 0)
                    break;
                ++item_map[item[1]];
            }
        }
        return res;
    }
};

[-数组]
class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        size_t len = values.size();
        vector<vector<int>> items;
        for (size_t i = 0; i < len; ++i)
            items.push_back({values[i], labels[i]});
        
        sort(items.begin(), items.end(), [](vector<int>& a, vector<int>& b) {return b[0] < a[0];});
        int label_count[20001] = {0};
        int res = 0;
        for (const auto& item : items) {
            if (label_count[item[1]] < use_limit) {
                res += item[0];
                if (--num_wanted == 0)
                    break;
                ++label_count[item[1]];
            }
        }
        return res;
    }
};

Python3代码

[-字典]
class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
        list_len = len(values)
        items = [(values[i], labels[i]) for i in range(list_len)]
        label_count, res = {}, 0
        for item in sorted(items, key=lambda item: item[0], reverse=True):
            count = 0 if item[1] not in label_count else label_count[item[1]]
            if count < use_limit:
                res += item[0]
                num_wanted -= 1
                if not num_wanted:
                    break
                label_count[item[1]] = count + 1
        return res

[-列表]
class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
        list_len = len(values)
        items = [(values[i], labels[i]) for i in range(list_len)]
        label_count, res = [0 for i in range(20001)], 0
        for item in sorted(items, key=lambda item: item[0], reverse=True):
            if label_count[item[1]] < use_limit:
                res += item[0]
                num_wanted -= 1
                if not num_wanted:
                    break
                label_count[item[1]] += 1
        return res

统计信息

通过次数	提交次数	AC比率
4076	7425	54.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言