LEETCODE 1338. Reduce Array Size to The Half 解题思路分析

题目大意：

数组大小减半

给你一个整数数组 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^5
• arr.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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1338-reduce-array-size-to-the-half-解题思路分析/