Medium

题目描述

给你一个整数数组 arr 和一个整数 k。现需要从数组中恰好移除 k 个元素，请找出剩余数组中唯一整数的最少数目。

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除单个 4，只剩下 5。

示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：移除 4、2 和两个 1 中的一个或三个 3 中的一个。1 和 3 将会保留下来。

提示：

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length

提示：

  • 使用映射来统计数组中数字的频次。
  • 一个最优策略是优先移除计数最小的数字。

解题思路

这是一个经典的贪心问题。要使剩余的唯一整数个数最少，我们应该优先移除出现次数较少的数字。

解题思路：

  1. 统计频次：使用哈希表统计每个数字在数组中的出现次数。

  2. 贪心策略：将所有数字按照出现频次从小到大排序。优先移除出现次数最少的数字，这样可以用最少的移除次数来减少唯一整数的个数。

  3. 模拟移除过程：按照频次从小到大的顺序，依次尝试完全移除每个唯一数字。如果剩余的移除次数 k 足够移除当前数字的所有实例，就完全移除；否则部分移除，并停止处理。

  4. 计算结果：最终剩余的唯一整数个数就是没有被完全移除的数字种类数。

这种贪心策略的正确性在于：要减少唯一整数的个数，必须完全移除某个数字的所有实例。因此，优先移除出现次数少的数字可以用更少的操作次数达到减少唯一整数个数的目标。

时间复杂度主要由排序决定，空间复杂度主要由哈希表存储频次信息决定。

代码实现

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        
        vector<int> counts;
        for (auto& p : freq) {
            counts.push_back(p.second);
        }
        
        sort(counts.begin(), counts.end());
        
        int uniqueCount = counts.size();
        for (int count : counts) {
            if (k >= count) {
                k -= count;
                uniqueCount--;
            } else {
                break;
            }
        }
        
        return uniqueCount;
    }
};

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        from collections import Counter
        
        freq = Counter(arr)
        counts = sorted(freq.values())
        
        unique_count = len(counts)
        for count in counts:
            if k >= count:
                k -= count
                unique_count -= 1
            else:
                break
        
        return unique_count

public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        var freq = new Dictionary<int, int>();
        foreach (int num in arr) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        var counts = freq.Values.ToArray();
        Array.Sort(counts);
        
        int uniqueCount = counts.Length;
        foreach (int count in counts) {
            if (k >= count) {
                k -= count;
                uniqueCount--;
            } else {
                break;
            }
        }
        
        return uniqueCount;
    }
}

var findLeastNumOfUniqueInts = function(arr, k) {
    const freq = new Map();
    for (const num of arr) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    const counts = Array.from(freq.values()).sort((a, b) => a - b);
    
    let uniqueCount = counts.length;
    for (const count of counts) {
        if (k >= count) {
            k -= count;
            uniqueCount--;
        } else {
            break;
        }
    }
    
    return uniqueCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
贪心 + 排序O(n log m)，其中 n 是数组长度，m 是唯一数字个数O(m)，用于存储频次信息

相关题目