[LeetCode] 每日一题 1338. 数组大小减半

题目链接

题目描述

给你一个整数数组 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}，结果数组为空。

提示

• 1 <= arr.length <= 10^5

• arr.length 为偶数

• 1 <= arr[i] <= 10^5

题解

解题思路

1. 统计每个数字的频次：首先，我们需要统计数组中每个数字出现的频次。可以使用哈希表（HashMap）来记录每个数字的出现次数。

2. 排序频次：将所有数字的出现次数存入一个列表中，并按出现频次从高到低排序。这是因为我们希望尽量删除频次高的数字，以达到最小删除集合的目的。

3. 删除元素：从高频数字开始删除，直到已删除的元素数量大于等于数组的一半。这时，删除的数字集合的大小就是答案。

4. 返回答案：通过遍历排序后的频次列表，累加被删除的元素的数量，直到达到数组大小的一半为止。返回删除的数字集合的大小。

代码实现

class Solution {
    public int minSetSize(int[] arr) {
        int ans = 0;  // 记录最小集合的大小
        HashMap<Integer, Integer> nums = new HashMap<>();  // 用于存储每个数字的出现次数
        
        // 统计每个数字的出现次数
        for (int num : arr) {
            nums.put(num, nums.getOrDefault(num, 0) + 1);
        }
        
        // 将频次列表转化为ArrayList，并按照频次从高到低排序
        List<Integer> list = new ArrayList<>(nums.values());
        list.sort(Collections.reverseOrder());
        
        int count = 0;  // 记录已删除的元素总数
        
        // 遍历排序后的频次列表，累加删除的元素数量
        for (int i = 0; i < list.size(); i++) {
            int temp = list.get(i);  // 当前数字的出现次数
            count += temp;  // 累加已删除的元素数量
            ans++;  // 删除一个数字，集合大小加1
            if (count * 2 >= arr.length) {
                // 如果已删除的元素数已经达到或超过一半，返回当前集合的大小
                return ans;
            }
        }
        
        return ans;  // 返回答案
    }
}

复杂度分析

• 时间复杂度：

  • 创建哈希表并统计频次需要遍历整个数组，时间复杂度为 O(n)，其中 n 是数组的长度。

  • 将哈希表的值转换为列表，并进行排序，时间复杂度为 O(k log k)，其中 k 是不同数字的数量（k ≤ n）。

  • 最终，遍历频次列表来累加删除的元素数量，时间复杂度为 O(k)。

  • 因此，总的时间复杂度为 O(n + k log k)，在最坏情况下，k 也可以接近 n，所以总体时间复杂度为 O(n log n)。

• 空间复杂度：

  • 哈希表 nums 存储数字的频次，空间复杂度为 O(k)，其中 k 是不同数字的数量。

  • 列表 list 存储频次值，空间复杂度也是 O(k)。

  • 因此，总空间复杂度为 O(k)。

关键点解释

• HashMap<Integer, Integer>：用于统计每个数字在数组中出现的频次。键是数组中的数字，值是该数字的出现次数。

• ArrayList<>(nums.values())：将哈希表中的频次值转换为一个列表，方便进行排序操作。

• list.sort(Collections.reverseOrder())：按照频次从高到低排序，这样我们可以优先删除出现频次高的数字。

• count * 2 >= arr.length：在删除过程中，我们一直累加删除的数字数量，当删除的数字数量达到数组长度的一半时，我们可以停止，返回当前已删除的数字集合的大小。

总结

这道题的核心是通过频次统计和排序，优先删除频次高的数字，直到删除的数字数量达到数组总长度的一半。通过这种方式，我们能确保删除的数字集合的大小是最小的。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。