- Problem Description: 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 in S with label L is <= 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], num_wanted = 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], num_wanted = 3, use_limit = 2
- Output: 12
- Explanation: The subset chosen is the first, second, and third item.
今天周赛这道题没做出来, 当时想到了才有贪心的思想, 但是想得过于复杂, 想对每一个 label 单独做一个优先队列, 用一个 map 来映射 label 和对应的优先队列, 另一个 map 来映射 label 和个数.
后来想到其实一个优先队列和一个记录 label 对应个数的 map 就可以解决.
代码如下:
- public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
- PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (values[b] - values[a]));
- for(int i = 0; i <values.length; i++) {
- pq.offer(i);
- }
- Map<Integer, Integer> labelCounter = new HashMap<>();
- int res = 0;
- while(!pq.isEmpty() && num_wanted> 0) {
- int index = pq.poll();
- int value = values[index];
- int label = labels[index];
- if(labelCounter.getOrDefault(label, 0) < use_limit) {
- res += value;
- num_wanted--;
- labelCounter.put(label, labelCounter.getOrDefault(label, 0) + 1);
- } else {
- continue;
- }
- }
- return res;
- }
来源: http://www.bubuko.com/infodetail-3094896.html