每日一题：受标签影响的最大值 - 刷题题解

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

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

一个子集的分数是该子集的值之和。返回子集 s 的最大分数。

题目链接：https://leetcode.cn/problems/largest-values-from-labels/

整体思路就是贪心，即 “每次都选择能选到的最大的数”，那么需要满足一下两个条件：

	class Solution {
	public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
	int n = values.length;
	int[][] arr = new int[n][2];

	for (int i = 0; i < n; ++i) {
	arr[i][0] = values[i];
	arr[i][1] = labels[i];
	}

	Arrays.sort(arr, (o1, o2) -> o2[0] - o1[0]);

	HashMap<Integer, Integer> cntMap = new HashMap<>();
	int select = 0;
	int score = 0;
	for (int i = 0; i < n; ++i) {
	if (select >= numWanted) break;
	int cnt = cntMap.getOrDefault(arr[i][1], 0);
	if (cnt >= useLimit) continue;
	score += arr[i][0];
	cntMap.put(arr[i][1], cnt + 1);
	++select;
	}

	return score;
	}
	}