文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题受标签影响的最大值出处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}nvalues.lengthlabels.length1 ≤ n ≤ 2 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤n≤2×1040 ≤ 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×1041 ≤ 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){intmaxScore0;intnvalues.length;int[][]valuesLabelsnewint[n][2];for(inti0;in;i){valuesLabels[i][0]values[i];valuesLabels[i][1]labels[i];}Arrays.sort(valuesLabels,(a,b)-b[0]-a[0]);MapInteger,IntegerlabelCountsnewHashMapInteger,Integer();for(inti0;innumWanted0;i){intvaluevaluesLabels[i][0],labelvaluesLabels[i][1];intcountlabelCounts.getOrDefault(label,0);if(countuseLimit){maxScorevalue;labelCounts.put(label,count1);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)的空间。
