526互联

[LeetCode] 1090. Largest Values From Labels

发布时间 2023-05-24 01:03:40作者: CNoodle

There is a set of n items. You are given two integer arrays values and labels where the value and the label of the ith element are values[i] and labels[i] respectively. You are also given two integers numWanted and useLimit.

Choose a subset s of the n elements such that:

  • The size of the subset s is less than or equal to numWanted.
  • There are at most useLimit items with the same label in s.

The score of a subset is the sum of the values in the subset.

Return the maximum score of a subset s.

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth items.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third items.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
Output: 16
Explanation: The subset chosen is the first and fourth items.

Constraints:

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

受标签影响的最大值。

我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

从 n 个元素中选择一个子集 s :

子集 s 的大小 小于或等于 numWanted 。
s 中 最多 有相同标签的 useLimit 项。
一个子集的 分数 是该子集的值之和。

返回子集 s 的最大 分数 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-values-from-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心 + 排序。题意写的比较绕，为了尽可能地得到更多的分数，我们肯定是要对 values 数组排序的。但是不能单单对 values 数组排序，这样会丢掉每个分数的 label 信息，所以这里我选择创建一个二维数组，将题目给的两个一维数组放进去。然后我对这个二维数组按分数从高到低排序，这样分数高的元素在前。

此时我们试着将每个元素的 value 一个个地累加，累加的时候注意，全局被累加的元素的个数不能大于 numWanted，同时 label 相同的元素个数不能大于 useLimit。

时间O(nlogn)

空间O(mn)

Java实现

 1 class Solution {
 2     public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
 3         int len = values.length;
 4         int[][] items = new int[len][2];
 5         for (int i = 0; i < len; i++) {
 6             items[i][0] = values[i];
 7             items[i][1] = labels[i];
 8         }
 9 
10         // Arrays.sort(items, Comparator.comparingInt(i -> -i[0]));
11         Arrays.sort(items, (a, b) -> b[0] - a[0]);
12         HashMap<Integer, Integer> map = new HashMap<>();
13         int res = 0;
14         for (int[] item : items) {
15             int labelCount = map.getOrDefault(item[1], 0);
16             if (labelCount < useLimit) {
17                 res += item[0];
18                 if (--numWanted == 0) {
19                     break;
20                 }
21                 map.put(item[1], labelCount + 1);
22             }
23         }
24         return res;
25     }
26 }

 

LeetCode 题目总结