贪心题目：数组大小减半

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题数组大小减半出处1338. 数组大小减半难度3 级题目描述要求给定一个整数数组arr \texttt{arr}arr。可以从中选出一个整数集合并删除这些整数在数组中的每次出现。返回至少能删除数组中的一半整数的整数集合的最小元素个数。示例示例 1输入arr [3,3,3,3,5,5,5,2,2,7] \texttt{arr [3,3,3,3,5,5,5,2,2,7]}arr [3,3,3,3,5,5,5,2,2,7]输出2 \texttt{2}2解释选择{3,7} \texttt{\{3,7\}}{3,7}将数组变成[5,5,5,2,2] \texttt{[5,5,5,2,2]}[5,5,5,2,2]长度为5 \texttt{5}5原数组长度的一半。大小为2 \texttt{2}2的可行集合有{3,5},{3,2},{5,2} \texttt{\{3,5\},\{3,2\},\{5,2\}}{3,5},{3,2},{5,2}。选择{2,7} \texttt{\{2,7\}}{2,7}是不可行的将数组变成[3,3,3,3,5,5,5] \texttt{[3,3,3,3,5,5,5]}[3,3,3,3,5,5,5]其长度大于原数组的一半。示例 2输入arr [7,7,7,7,7,7] \texttt{arr [7,7,7,7,7,7]}arr [7,7,7,7,7,7]输出1 \texttt{1}1解释只能选择集合{7} \texttt{\{7\}}{7}将数组变成空数组。数据范围1 ≤ arr.length ≤ 10 5 \texttt{1} \le \texttt{arr.length} \le \texttt{10}^\texttt{5}1≤arr.length≤105arr.length \texttt{arr.length}arr.length为偶数1 ≤ arr[i] ≤ 10 5 \texttt{1} \le \texttt{arr[i]} \le \texttt{10}^\texttt{5}1≤arr[i]≤105解法思路和算法遍历数组arr \textit{arr}arr得到每个元素的出现次数创建列表counts \textit{counts}counts存储每个元素的出现次数则counts \textit{counts}counts中的元素之和为数组arr \textit{arr}arr的长度问题转换成从counts \textit{counts}counts中选择最少的元素个数使得所选的元素之和至少为数组arr \textit{arr}arr的长度的一半。根据贪心思想在所选元素之和下界确定的情况下为了使所选元素的个数最少应从counts \textit{counts}counts按照从大到小的顺序依次选取元素直到选取的元素之和至少为数组arr \textit{arr}arr的长度的一半此时选取的元素个数即为从数组arr \textit{arr}arr中选出的集合的最小元素个数。贪心思想的正确性说明如下。假设从counts \textit{counts}counts按照从大到小的顺序选取元素时至少选取x xx个元素可以满足选取的元素之和至少为数组arr \textit{arr}arr的长度的一半用halfLength \textit{halfLength}halfLength表示数组arr \textit{arr}arr的长度的一半。如果将最大的x xx个元素中的任意一个元素换成更小的元素则选取的元素之和将减小此时选取的元素之和可能大于等于halfLength \textit{halfLength}halfLength也可能小于halfLength \textit{halfLength}halfLength如果小于halfLength \textit{halfLength}halfLength则需要选取更多元素才能满足选取的元素之和大于等于halfLength \textit{halfLength}halfLength此时选取的元素个数大于x xx。因此按照从大到小的顺序选取元素可以使选取的元素个数最少。具体做法是得到列表counts \textit{counts}counts之后将counts \textit{counts}counts按降序排序然后按从大到小的顺序遍历counts \textit{counts}counts选取元素直到选取的元素之和大于等于halfLength \textit{halfLength}halfLength时返回选取的元素个数即从数组arr \textit{arr}arr中选出的集合的最小元素个数。代码classSolution{publicintminSetSize(int[]arr){MapInteger,IntegercountsMapnewHashMapInteger,Integer();for(intnum:arr){countsMap.put(num,countsMap.getOrDefault(num,0)1);}ListIntegercountsnewArrayListInteger(countsMap.values());Collections.sort(counts,(a,b)-b-a);inthalfLengtharr.length/2;intremoveCount0;intminSize0;for(intcount:counts){removeCountcount;minSize;if(removeCounthalfLength){break;}}returnminSize;}}复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)其中n nn是数组arr \textit{arr}arr的长度。计算每个元素的出现次数需要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是数组arr \textit{arr}arr的长度。哈希表和出现次数列表需要O ( n ) O(n)O(n)的空间。