题目描述

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

样例

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

限制

• $1 \leq arr.length \leq 10^5$
• $1 \leq arr[i] \leq 10^9$
• $0 \leq k \leq arr.length$

算法

(贪心) $O(nlog(n))$

1. 直觉：优先删除出现次数小的数字
2. 步骤：统计数字出现次数，出现次数按从小到大排序，依次枚举并删除，直到不能删除为止

时间复杂度

最坏情况下每个数只出现了一次，整个过程中统计出现次数时间复杂度为$O(n)$，排序时间复杂度为$O(nlog(n))$，因此总的时间复杂度为$O(nlog(n))$

C++ 代码

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> hash;
        for (auto x : arr) hash[x] ++ ;
        vector<int> cnt;
        for (auto x : hash) cnt.push_back(x.second);
        sort(cnt.begin(), cnt.end());
        int ret = cnt.size();
        for (int i = 0; i < cnt.size(); i ++ )
            if (k >= cnt[i]) {
                k -= cnt[i];
                ret -- ;
            } else break;
        return ret;
    }
};