Medium

题目描述

给你 n 个物品的价值和标签，分别用整数数组 values 和 labels 表示。同时给你两个整数 numWanted 和 useLimit。

你的任务是从这些物品中选取一个子集，使得它们的价值总和最大，同时满足：

  • 物品的数量最多为 numWanted
  • 相同标签的物品数量最多为 useLimit

返回最大价值总和。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出：9
解释：选取的子集是第 1、3、5 个物品，价值总和为 5 + 3 + 1 = 9

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出：12
解释：选取的子集是第 1、2、3 个物品，价值总和为 5 + 4 + 3 = 12

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出：16
解释：选取的子集是第 1、4 个物品，价值总和为 9 + 7 = 16

约束条件：

  • n == values.length == labels.length
  • 1 <= n <= 2 * 10^4
  • 0 <= values[i], labels[i] <= 2 * 10^4
  • 1 <= numWanted, useLimit <= n

解题思路

这是一个典型的贪心算法问题。我们需要在满足约束条件的前提下，选择价值总和最大的物品子集。

解题思路：

  1. 贪心策略：为了获得最大价值，我们应该优先选择价值最高的物品。但是由于存在标签限制（每个标签最多使用 useLimit 次），我们需要在选择时进行约束检查。

  2. 排序：首先将物品按价值从高到低排序。为了保持价值和标签的对应关系，我们创建索引数组进行排序。

  3. 哈希表计数：使用哈希表记录每个标签已经使用的次数，确保不超过 useLimit。

  4. 贪心选择：遍历排序后的物品，对于每个物品：

    • 如果已选择的物品数量达到 numWanted，停止选择
    • 如果该物品的标签使用次数未达到 useLimit，则选择该物品
    • 更新标签计数和总价值

时间复杂度分析： 排序需要 O(n log n)，遍历选择需要 O(n)，总体为 O(n log n)。

代码实现

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        int n = values.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return values[i] > values[j];
        });
        
        unordered_map<int, int> labelCount;
        int result = 0;
        int selected = 0;
        
        for (int i : indices) {
            if (selected == numWanted) break;
            
            if (labelCount[labels[i]] < useLimit) {
                result += values[i];
                labelCount[labels[i]]++;
                selected++;
            }
        }
        
        return result;
    }
};

class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
        # 创建索引数组并按价值降序排序
        indices = list(range(len(values)))
        indices.sort(key=lambda i: values[i], reverse=True)
        
        label_count = {}
        result = 0
        selected = 0
        
        for i in indices:
            if selected == numWanted:
                break
                
            label = labels[i]
            if label_count.get(label, 0) < useLimit:
                result += values[i]
                label_count[label] = label_count.get(label, 0) + 1
                selected += 1
        
        return result

public class Solution {
    public int LargestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.Length;
        int[] indices = new int[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        Array.Sort(indices, (i, j) => values[j].CompareTo(values[i]));
        
        Dictionary<int, int> labelCount = new Dictionary<int, int>();
        int result = 0;
        int selected = 0;
        
        foreach (int i in indices) {
            if (selected == numWanted) break;
            
            int label = labels[i];
            labelCount.TryGetValue(label, out int count);
            
            if (count < useLimit) {
                result += values[i];
                labelCount[label] = count + 1;
                selected++;
            }
        }
        
        return result;
    }
}

var largestValsFromLabels = function(values, labels, numWanted, useLimit) {
    const items = values.map((value, i) => [value, labels[i]]);
    items.sort((a, b) => b[0] - a[0]);
    
    const labelCount = new Map();
    let sum = 0;
    let count = 0;
    
    for (const [value, label] of items) {
        if (count >= numWanted) break;
        
        const currentCount = labelCount.get(label) || 0;
        if (currentCount < useLimit) {
            sum += value;
            count++;
            labelCount.set(label, currentCount + 1);
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要开销在排序，其中 n 是物品数量
空间复杂度O(n)索引数组和哈希表的空间开销

相关题目