友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1090. Largest Values From Labels
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 inSwith labelLis<= 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], = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.Example 2:
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.Example 3:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.Example 4:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.Note:
-
1 ⇐ values.length == labels.length ⇐ 20000 -
0 ⇐ values[i], labels[i] ⇐ 20000 -
1 ⇐ num_wanted, use_limit ⇐ values.length
思路分析
初看以为是回溯（回溯也可以，能通过大部分的测试），看答案之后，可以通过排序来解决。
再次想想，感觉回溯解决不了问题，它没办法保证首先选中的就是大数。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-25 19:36:28
*/
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
int length = values.length;
Integer[] id = new Integer[length];
for (int i = 0; i < length; i++) {
id[i] = i;
}
// 倒序排列，把大数放在前面
Arrays.sort(id, (a, b) -> Integer.compare(values[b], values[a]));
Map<Integer, Integer> cnt = new HashMap<>();
int result = 0;
int choose = 0;
for (int i = 0; i < length && choose < numWanted; i++) {
int label = labels[id[i]];
if (cnt.getOrDefault(label, 0) == useLimit) {
continue;
}
result += values[id[i]];
choose++;
cnt.put(label, cnt.getOrDefault(label, 0) + 1);
}
return result;
}