You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.
1090. 受标签影响的最大值 - Largest Values From Labels

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

. 2 min read

【贪心】

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

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})$