class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
}
};
1090. 受标签影响的最大值
我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。
从 n 个元素中选择一个子集 s :
s 的大小 小于或等于 numWanted 。s 中 最多 有相同标签的 useLimit 项。一个子集的 分数 是该子集的值之和。
返回子集 s 的最大 分数 。
示例 1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1 输出：9 解释：选出的子集是第一项，第三项和第五项。
示例 2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2 输出：12 解释：选出的子集是第一项，第二项和第三项。
示例 3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1 输出：16 解释：选出的子集是第一项和第四项。
提示：
n == values.length == labels.length1 <= n <= 2 * 1040 <= values[i], labels[i] <= 2 * 1041 <= numWanted, useLimit <= n原站题解
python3 解法, 执行用时: 80 ms, 内存消耗: 19.6 MB, 提交时间: 2022-12-09 16:31:54
'''
贪心策略，把value全部按照数值降序排，从大到小
选数据，只要这个数据对应的label计数值不超过use_limit
就可以进行选择， 直到遍历结束或者是数量选够为止
'''
from typing import List
from collections import Counter
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
l = [(val, label) for val, label in zip(values, labels)]
l.sort(reverse = True)
c = Counter()
cnt = 0
sum = 0
for val, label in l:
if cnt == num_wanted:
break
if c[label] < use_limit:
c[label] += 1
sum += val
cnt += 1
return sum
python3 解法, 执行用时: 72 ms, 内存消耗: 19.5 MB, 提交时间: 2022-12-09 16:31:07
from heapq import nlargest
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
label_value = {}
for v, l in zip(values, labels):
label_value[l] = label_value.get(l, [])+[v]
res = []
for k, v in label_value.items():
res.extend(nlargest(use_limit, v))
return sum(nlargest(num_wanted, res))
python3 解法, 执行用时: 92 ms, 内存消耗: 18.4 MB, 提交时间: 2022-12-09 16:30:47
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
list_len = len(values)
items = [(values[i], labels[i]) for i in range(list_len)]
label_count, res = [0 for i in range(20001)], 0
for item in sorted(items, key=lambda item: item[0], reverse=True):
if label_count[item[1]] < use_limit:
res += item[0]
num_wanted -= 1
if not num_wanted:
break
label_count[item[1]] += 1
return res
java 解法, 执行用时: 17 ms, 内存消耗: 41.8 MB, 提交时间: 2022-12-09 16:30:32
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
int len = values.length;
int[][] items = new int[len][2];
for (int i = 0; i < len; ++i) {
items[i][0] = values[i];
items[i][1] = labels[i];
}
Arrays.sort(items, Comparator.comparingInt(i -> -i[0]));
HashMap<Integer, Integer> map = new HashMap<>();
int res = 0;
for (int[] item : items) {
int label_count = map.getOrDefault(item[1], 0);
if (label_count < use_limit) {
res += item[0];
if (--num_wanted == 0)
break;
map.put(item[1], label_count + 1);
}
}
return res;
}
}
java 解法, 执行用时: 15 ms, 内存消耗: 42.7 MB, 提交时间: 2022-12-09 16:30:13
//既然题目说了label的值的范围是[0, 20000]，那就将HashMap改为数组，速度更快。
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
int len = values.length;
int[][] items = new int[len][2];
for (int i = 0; i < len; ++i) {
items[i][0] = values[i];
items[i][1] = labels[i];
}
Arrays.sort(items, Comparator.comparingInt(i -> -i[0]));
int[] label_count = new int[20001];
int res = 0;
for (int[] item : items) {
if (label_count[item[1]] < use_limit) {
res += item[0];
if (--num_wanted == 0)
break;
++label_count[item[1]];
}
}
return res;
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 19.4 MB, 提交时间: 2022-12-09 16:29:45
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
list_len = len(values)
items = [(values[i], labels[i]) for i in range(list_len)]
label_count, res = {}, 0
for item in sorted(items, key=lambda item: item[0], reverse=True):
count = 0 if item[1] not in label_count else label_count[item[1]]
if count < use_limit:
res += item[0]
num_wanted -= 1
if not num_wanted:
break
label_count[item[1]] = count + 1
return res