贪心题目：受标签影响的最大值

题目

标题和出处

标题：受标签影响的最大值

出处：1090. 受标签影响的最大值

难度

5 级

题目描述

要求

有一个n \texttt{n}n项的集合。给定两个整数数组values \texttt{values}values和labels \texttt{labels}labels，第i \texttt{i}i个元素的值和标签分别是values[i] \texttt{values[i]}values[i]和labels[i] \texttt{labels[i]}labels[i]。另外给定两个整数numWanted \texttt{numWanted}numWanted和useLimit \texttt{useLimit}useLimit。

从n \texttt{n}n个元素中选择一个符合下列要求的子集s \texttt{s}s：

• 子集s \texttt{s}s的大小小于或等于numWanted \texttt{numWanted}numWanted。
• 子集s \texttt{s}s中的相同标签的元素最多有useLimit \texttt{useLimit}useLimit个。

一个子集的分数是该子集的值之和。

返回子集s \texttt{s}s的最大分数。

示例

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1 \texttt{values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1}values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出：9 \texttt{9}9
解释：选出的子集是第一项、第三项和第五项。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2 \texttt{values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2}values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出：12 \texttt{12}12
解释：选出的子集是第一项、第二项和第三项。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1 \texttt{values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1}values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出：16 \texttt{16}16
解释：选出的子集是第一项和第四项。

数据范围

• n = values.length = labels.length \texttt{n} = \texttt{values.length} = \texttt{labels.length}n=values.length=labels.length
• 1 ≤ n ≤ 2 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤n≤2×104
• 0 ≤ values[i], labels[i] ≤ 2 × 10 4 \texttt{0} \le \texttt{values[i], labels[i]} \le \texttt{2} \times \texttt{10}^\texttt{4}0≤values[i], labels[i]≤2×104
• 1 ≤ numWanted, useLimit ≤ n \texttt{1} \le \texttt{numWanted, useLimit} \le \texttt{n}1≤numWanted, useLimit≤n

解法

思路和算法

为了得到所选子集的最大分数，可以使用贪心策略。

由于所有的元素值都是非负整数，当子集的元素个数小于numWanted \textit{numWanted}numWanted时，在不违反规则的情况下将一个新元素加入子集之后，子集的分数一定会增加或不变，不可能减少，因此应该在不违反规则的情况下将尽可能多的元素加入子集。

如果没有相同标签的元素最多useLimit \textit{useLimit}useLimit个的限制，则应该选值最大的numWanted \textit{numWanted}numWanted个元素加入子集，此时子集的分数最大，如果将其中的任意元素换成更小的元素，则子集的分数不会增加，只会减少。在有标签限制的情况下，如果同一个标签的元素个数超过useLimit \textit{useLimit}useLimit，则不能选该标签的所有元素，根据贪心策略，在限定可选元素个数上限的情况下，应选值最大的元素，否则子集的分数不可能更大。

为了按照从大到小的顺序选取元素，同时保留每个元素对应的标签信息，需要创建二维数组记录元素值与标签，将二维数组按照元素值降序排序。遍历排序后的数组，使用哈希表记录每个标签下选取的元素个数，对于每个元素，得到元素的值与标签，执行如下操作。

• 如果当前标签下选取的元素个数已经达到useLimit \textit{useLimit}useLimit，则跳过该元素。

• 如果当前标签下选取的元素个数小于useLimit \textit{useLimit}useLimit，则选取当前元素，将元素值加到子集的分数，将当前标签下选取的元素个数加1 11，将numWanted \textit{numWanted}numWanted减1 11。

当遍历结束或者numWanted \textit{numWanted}numWanted减少到0 00时，结束操作，此时即可得到子集的最大分数。

代码

classSolution{publicintlargestValsFromLabels(int[]values,int[]labels,intnumWanted,intuseLimit){intmaxScore=0;intn=values.length;int[][]valuesLabels=newint[n][2];for(inti=0;i<n;i++){valuesLabels[i][0]=values[i];valuesLabels[i][1]=labels[i];}Arrays.sort(valuesLabels,(a,b)->b[0]-a[0]);Map<Integer,Integer>labelCounts=newHashMap<Integer,Integer>();for(inti=0;i<n&&numWanted>0;i++){intvalue=valuesLabels[i][0],label=valuesLabels[i][1];intcount=labelCounts.getOrDefault(label,0);if(count<useLimit){maxScore+=value;labelCounts.put(label,count+1);numWanted--;}}returnmaxScore;}}

复杂度分析

• 时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，其中n nn是数组values \textit{values}values和labels \textit{labels}labels的长度。创建二维数组需要O ( n ) O(n)O(n)的时间，排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间，排序之后遍历二维数组需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。

• 空间复杂度：O ( n ) O(n)O(n)，其中n nn是数组values \textit{values}values和labels \textit{labels}labels的长度。二维数组和哈希表需要O ( n ) O(n)O(n)的空间。