1. 受标签影响的最大值 - Largest Values From Labels

【贪心】

Problem Link

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

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

  • |S| <= num_wanted
  • 对于任意的标签 L,子集 S 中标签为 L 的项的数目总满足 <= use_limit。返回子集 S 的最大可能的 和。

Example:

示例 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

解释:选出的子集是第一项,第二项和第四项。


Analysis

这道题目读懂了就不难(我竞赛的时候就钻牛角尖了)。

第一点要求 |S| <= num_wanted 是说选择的总数不能超过 num_wanted

第二点要求是说同一个标签下的项,选择的数量不能超过 use_limit

理解了这两点就很清楚了,这是一个简单的贪心策略能够解决的问题,只需要将其按照价值排列,优先选择价值高的即可。

下面提供一种直接实现的思路。

Solution

执行用时 :107 ms, 在所有 Java 提交中击败了44.00%的用户

内存消耗 :49.9 MB, 在所有 Java 提交中击败了100.00%的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        // 边界情况
        if (num_wanted == 0 || use_limit == 0) {
            return 0;
        }
        int len = values.length;
        int[][] pairs = new int[len][2];
        for(int i = 0; i < len; i++){
            pairs[i][0] = values[i];
            pairs[i][1] = labels[i];
        }
        // 按照 value 降序排列
        Arrays.sort(pairs,(o1,o2)-> o2[0]-o1[0]);
        // 记录当前label选择的数量
        int[] numLabel = new int[20001];  // max{label} = 20000
        int ans = 0;
        // 记录选择的总数 |S|
        int cnt = 0;
        for(int i = 0; i < len; i++){
            int lab = pairs[i][1];
            if(numLabel[lab] >= use_limit)
                continue;
            ans += pairs[i][0];
            numLabel[lab]++;
            cnt++;
            if(cnt >= num_wanted)
                return ans;
        }
        return ans;
        
    }
}

复杂度分析

时间:$O(NlogN)$ $N = len(values)$

空间:$O(max{label})$