LC.P1090[受标签影响的最大值]

方法一：贪心+排序+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        int[][] index = new int[n][2];
        for (int i = 0; i < n; ++i) {
            index[i] = new int[]{values[i], labels[i]};
        }
        Arrays.sort(index, (a, b) -> b[0] - a[0]);
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0, cnt = 0;
        for (int i = 0; i < n && cnt < numWanted; ++i) {
            int value = index[i][0], label = index[i][1];
            if (map.getOrDefault(label, 0) < useLimit) {
                map.merge(label, 1, Integer::sum);
                ++cnt;
                ans += value;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$