难度: Medium
给你一个整数数组 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 <= 105arr.length 为偶数1 <= arr[i] <= 105运行时间: 60 ms
内存: 32.4 MB
from collections import Counter
from typing import List
class Solution:
def minSetSize(self, arr: List[int]) -> int:
n = len(arr)
target = n // 2
counter = Counter(arr)
sorted_counts = sorted(counter.values(), reverse=True)
accumulated = 0
result = 0
for count in sorted_counts:
accumulated += count
result += 1
if accumulated >= target:
return result
return result
该题目的核心是找到一个最小的整数集合，使得从数组中删除这些整数后，数组的大小至少减少一半。首先，我们使用 Counter 类来统计数组中每个整数的出现频次。接着，将得到的频次进行降序排序。这样，选择频次最高的数，我们可以更快地减少数组的大小。我们从频次最高的元素开始，逐个累加这些元素的出现次数，直到这个累加值达到或超过原数组长度的一半。此时，累加的元素个数就是所需的最小集合大小。
时间复杂度: O(n log n)
空间复杂度: O(n)
from collections import Counter
from typing import List
class Solution:
def minSetSize(self, arr: List[int]) -> int:
n = len(arr) # 数组的长度
target = n // 2 # 目标是减少到原长度的一半
counter = Counter(arr) # 统计各元素的频次
sorted_counts = sorted(counter.values(), reverse=True) # 频次降序排序
accumulated = 0 # 累计已删除的元素数量
result = 0 # 已选择的最小集合大小
for count in sorted_counts: # 遍历排序后的频次
accumulated += count # 累加频次
result += 1 # 增加选择的集合大小
if accumulated >= target: # 如果达到或超过目标
return result # 返回集合大小
return result # 如果所有元素都被考虑过，返回最终结果
在解法中选择将频次进行降序排序是为了尽快达到减半数组大小的目标。通过优先选择出现频次最高的元素，可以最快地减少数组中的元素总数，从而用尽可能少的不同元素数量来达到或超过减半的要求。如果使用升序排序或保持原有顺序，则可能需要选择更多的元素才能达到目标，这样做效率较低。
是的，算法中提到的累加频次能确保在最坏情况下仍能找到满足条件的最小集合。算法通过累加排序后的频次列表，直到累加值达到或超过数组长度的一半。由于排序确保了我们优先考虑出现次数最多的元素，这种方式在任何情况下都可以最小化需要选择的元素集合大小，确保找到的是最小集合。
如果数组中包含的某个重复元素的数量刚好等于数组长度的一半，那么算法的输出将是1。这是因为该元素的出现频次本身就达到了减少数组到一半大小的要求，所以只需选择这一个元素即可实现目标。
算法本身在每次累加一个元素的频次后都会检查是否已经达到或超过目标（数组长度的一半）。这意味着一旦发现某个频次足够大，能够单独满足减半条件，算法会立即停止累加并返回当前已选择的元素个数。因此，算法确实有机制优化以避免不必要的累加操作，即通过逐个检查并及时终止循环来实现。