题目大意：
数组大小减半
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。 示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。 示例 3：
输入：arr = [1,9] 输出：1
示例 4：
输入：arr = [1000,1000,3,7] 输出：1
示例 5：
输入：arr = [1,2,3,4,5,6,7,8,9,10] 输出：5
提示：
1 <= arr.length <= 10^5arr.length为偶数1 <= arr[i] <= 10^5
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1338
解题思路分析：
题目大意是说，我们每一次操作可以将数组内某一种相同数字全部删除，问最少删除多少次之后，数组内元素数量能小于等于原先的一半。因为是求最少操作次数，所以每一次操作尽量删除更过的元素一定是最优方案。
我们先统计出数组中每种数字的个数，然后将个数排序，从个数最多的开始删除，当累加删除个数大于等于原数组元素个数一半时，操作次数即是返回结果。
实现代码：
public int minSetSize(int[] arr) {
// 数组元素个数的一半
int halfLength = arr.length/2;
// 统计每种数字出现的个数
int[] count=new int[100001];
for(int n : arr){
count[n]++;
}
// 排序个数数组
Arrays.sort(count);
// 从个数最多的开始删除
// 当前删除的个数
int deleteCount=0;
for(int i=100000;i>=0;i--){
// 累加删除个数
deleteCount+=count[i];
// 当删除个数大于等于数组元素个数的一半时
if(deleteCount>=halfLength){
// 返回操作次数
return 100001-i;
}
}
return 0;
} 本题解法执行时间为23ms。
Runtime: 23 ms, faster than 97.79% of Java online submissions for Reduce Array Size to The Half.
Memory Usage: 55.9 MB, less than 100.00% of Java online submissions for Reduce Array Size to The Half.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1338-reduce-array-size-to-the-half-解题思路分析/