1090.受标签影响的最大值

题目

受标签影响的最大值

思路

使用vector<pair<int, int>> 将 values 和 labels 对应起来，然后按照 values 从大到小进行排序，每次在满足对应的标签没有达到上限时（使用unordered_map进行计数），优先取最大的即可。

题解

• 题解1

class Solution {
public:
    vector<pair<int, int>> arr;
    unordered_map<int, int> hsp;
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        for(int i = 0; i < values.size(); i ++){
            arr.push_back(make_pair(values[i], labels[i]));
        }
        sort(arr.begin(), arr.end(), [](pair<int, int> &a, pair<int, int> &b){  // 将arr数组从大到小进行排序
            return a.first > b.first;
        });
        int res = 0;
        for(int i = 0; i < arr.size() && numWanted; i++){
            if(hsp[arr[i].second] < useLimit){
                hsp[arr[i].second] ++;
                res += arr[i].first;
                numWanted--;
            }
        }
        return res;
    }
};

• 时间复杂度：O(n \ log n)，其中 n 为 values* 的大小，主要是 sort()函数的时间发复杂度
• 空间复杂度：O(n)，数组和哈希表对应的空间

执行用时：24 ms, 在所有 C++ 提交中击败了80.30%的用户

内存消耗：19.8 MB, 在所有 C++ 提交中击败了65.15%的用户

通过测试用例：81 / 81