题目描述

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

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

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

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

样例

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

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

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

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

算法

(贪心) $O(n \log n)$

1. 将物品集合按照 value 从大到小排序，按顺序挑选，如果 L 超出了 use_limit 则不选当前的数字。
2. 直到遍历完了整个集合或挑选的总数目达到了 num_wanted。

时间复杂度

• 排序后扫描的时间复杂度为 $O(n \log n)$。
• 判断标签使用次数采用哈希表，单次查询更新的时间为常数。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外的空间对两个关键字同时排序，需要空间记录每个标签的使用次数，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        int n = values.size();
        vector<pair<int, int>> p;
        for (int i = 0; i < n; i++)
            p.emplace_back(make_pair(values[i], labels[i]));
        sort(p.begin(), p.end());
        reverse(p.begin(), p.end());

        unordered_map<int, int> used;
        int num = 0, ans = 0;
        for (int i = 0; i < n; i++)
            if (used[p[i].second] < use_limit) {
                used[p[i].second]++;
                ans += p[i].first;
                num++;
                if (num == num_wanted)
                    break;
            }

        return ans;
    }
};