• 1338. 数组大小减半

• 标签：贪心、数组、哈希表、排序、堆（优先队列）

• 难度：中等

题目链接

• 1338. 数组大小减半 - 力扣

题目大意

描述：给定过一个整数数组 $arr$。你可以从中选出一个整数集合，并在数组 $arr$ 删除所有整数集合对应的数。

要求：返回至少能删除数组中的一半整数的整数集合的最小大小。

说明：

• $1 \le arr.length \le 10^5$。
• $arr.length$ 为偶数。
• $1 \le arr[i] \le 10^5$。

示例：

• 示例 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：贪心算法

对于选出的整数集合中每一个数 $x$ 来说，我们会删除数组 $arr$ 中所有值为 $x$ 的整数。

因为题目要求我们选出的整数集合最小，所以在每一次选择整数 $x$ 加入整数集合时，我们都应该选择数组 $arr$ 中出现次数最多的数。

因此，我们可以统计出数组 $arr$ 中每个整数的出现次数，用哈希表存储，并依照出现次数进行降序排序。

然后，依次选择出现次数最多的数进行删除，并统计个数，直到删除了至少一半的数时停止。

最后，将统计个数作为答案返回。

思路 1：代码

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnts = Counter(arr)
        ans, cnt = 0, 0
        for num, freq in cnts.most_common():
            cnt += freq
            ans += 1
            if cnt * 2 >= len(arr):
                break

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log n)$，其中 $n$ 为数组 $arr$ 的长度。
• 空间复杂度：$O(n)$。