【Leetcode】1090. Largest Values From Labels（第141周周赛）（选择排序sort）

﹏ヽ暗。殇╰゛Y 2022-01-13 11:13 193阅读 0赞

We have a set of items: the `i`\-th item has value `values[i]` and label `labels[i]`.

Then, we choose a subset `S` of these items, such that:

*  `|S| <= num_wanted`
 *  For every label `L`, the number of items in `S`with label `L` is `<= use_limit`.

Return the largest possible sum of the subset `S`.

**Example 1:**

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

**Note:**

1.  `1 <= values.length == labels.length <= 20000`
2.  `0 <= values[i], labels[i] <= 20000`
3.  `1 <= num_wanted, use_limit <= values.length`

题目大意：

values中每个数对应一个标签。 num\_wanted表示为一共能够选取的个数，use\_limit表示一个类别最多能够选取的个数。求出value总和最大的值。

解题思路：

构建一个对应表，将value和label联系起来，然后按照value从大到小排序，遍历数组记录已选择的个数和每个类别的个数即可。

class Solution {
    public:
        int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
            vector<vector<int> > nums;
            for(int i=0;i<values.size();i++){
                vector<int> tmp_nums;
                tmp_nums.push_back(values[i]);
                tmp_nums.push_back(labels[i]);
                nums.push_back(tmp_nums);
            }
            
            sort(nums.begin(), nums.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] > b[0]; });
            int ans = 0;
            int ans_ji = 0;
            int maps[20000+100];
            memset(maps, 0, sizeof(maps));
            for(int i=0;i<values.size();i++){
                if(maps[nums[i][1]]<use_limit){
                    ans += nums[i][0];
                    maps[nums[i][1]]++;
                    ans_ji++;
                }
                    
                if(ans_ji==num_wanted) break;
            }
            
            return ans;
        }
    };