受标签影响的最大值【LC1090】
我们有一个
n项的集合。给出两个整数数组values和labels，第i个元素的值和标签分别是values[i]和labels[i]。还会给出两个整数numWanted和useLimit。从
n个元素中选择一个子集s:
- 子集
s的大小 小于或等于numWanted。s中 最多 有相同标签的useLimit项。一个子集的 分数 是该子集的值之和。
返回子集
s的最大 分数 。
思路
- 由于能够取的数有数量限制，因此我们应该优先取数值较大的数【局部最优】，以获得最大分数【全局最优】
- 由于相同标签只能选择
useLimit个数，因此需要使用哈希表记录每个标签已经取的数的个数。 - 将数组按照值降序排序，判断当前标签能否取，如果能那么取该数，不能直接跳至下一个数
- 实现
class Solution { public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) { int n = values.length; int[][] data = new int[n][2]; Map<Integer,Integer> map = new HashMap<>(); int res = 0; for (int i = 0; i < n; i++){ data[i][0] = values[i]; data[i][1] = labels[i]; } Arrays.sort(data, (o1, o2) -> o2[0] - o1[0]); int count = 0, i = 0; while (count < numWanted && i < n){ if (map.getOrDefault(data[i][1], 0) < useLimit){ count++; res += data[i][0]; map.put(data[i][1], map.getOrDefault(data[i][1], 0) + 1); } i++; } return res; } }
