企业官网建设流程全解析

题目

标题和出处

标题：数组大小减半

出处：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≤105
• arr.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){Map<Integer,Integer>countsMap=newHashMap<Integer,Integer>();for(intnum:arr){countsMap.put(num,countsMap.getOrDefault(num,0)+1);}List<Integer>counts=newArrayList<Integer>(countsMap.values());Collections.sort(counts,(a,b)->b-a);inthalfLength=arr.length/2;intremoveCount=0;intminSize=0;for(intcount:counts){removeCount+=count;minSize++;if(removeCount>=halfLength){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)的空间。