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}，结果数组为空。

提示：

  • 2 <= arr.length <= 10^5
  • arr.length 是偶数
  • 1 <= arr[i] <= 10^5

解题思路

这道题的核心思路是贪心策略：要用最少的整数删除至少一半的元素，应该优先选择出现频率最高的整数。

解题步骤：

  1. 统计频率：遍历数组，统计每个整数的出现次数
  2. 排序频率：将所有频率按降序排列，优先选择频率最高的整数
  3. 贪心选择：从频率最高的整数开始选择，累计删除的元素个数，直到达到数组长度的一半

算法分析：

  • 使用哈希表统计频率的时间复杂度为 O(n)
  • 对频率进行排序的时间复杂度为 O(k log k)，其中 k 是不同整数的个数
  • 贪心选择的时间复杂度为 O(k)

这种贪心策略是正确的，因为每次选择频率最高的整数能够最大化每一步的收益，从而用最少的选择达到目标。

推荐解法：哈希表统计 + 排序 + 贪心选择

代码实现

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        
        vector<int> frequencies;
        for (auto& pair : freq) {
            frequencies.push_back(pair.second);
        }
        
        sort(frequencies.rbegin(), frequencies.rend());
        
        int removed = 0;
        int setSize = 0;
        int target = arr.size() / 2;
        
        for (int f : frequencies) {
            removed += f;
            setSize++;
            if (removed >= target) {
                break;
            }
        }
        
        return setSize;
    }
};

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        from collections import Counter
        
        freq = Counter(arr)
        frequencies = sorted(freq.values(), reverse=True)
        
        removed = 0
        set_size = 0
        target = len(arr) // 2
        
        for f in frequencies:
            removed += f
            set_size += 1
            if removed >= target:
                break
        
        return set_size

public class Solution {
    public int MinSetSize(int[] arr) {
        var freq = new Dictionary<int, int>();
        foreach (int num in arr) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        var frequencies = freq.Values.OrderByDescending(x => x).ToList();
        
        int removed = 0;
        int setSize = 0;
        int target = arr.Length / 2;
        
        foreach (int f in frequencies) {
            removed += f;
            setSize++;
            if (removed >= target) {
                break;
            }
        }
        
        return setSize;
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var minSetSize = function(arr) {
    const freq = new Map();
    for (const num of arr) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    const frequencies = Array.from(freq.values()).sort((a, b) => b - a);
    
    let removed = 0;
    let setSize = 0;
    const target = Math.floor(arr.length / 2);
    
    for (const f of frequencies) {
        removed += f;
        setSize++;
        if (removed >= target) {
            break;
        }
    }
    
    return setSize;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k log k)n 为数组长度，k 为不同元素个数；统计频率 O(n)，排序 O(k log k)
空间复杂度O(k)哈希表和频率数组的空间，k 为不同元素个数