题目描述

给定一个整数数组 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 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

算法

(贪心) $O(n \log n)$

1. 尽可能的先移除重复次数较少的元素。
2. 将数组从小到大排序，计算出每个元素的频次，并将这些频次重新放入一个数组中。
3. 将 频次数组 从小到大排序，依次用 k 去减，最后就可以得到最多能消除的数字个数。

时间复杂度

• 排序原数组的时间复杂度为 $O(n \log n)$，由于 频次数组 的长度最多也为 $n$，故排序 频次数组 的时间复杂度也为 $O(n \log n)$。
• 最后线性遍历 频次数组 求答案，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储 频次数组。

C++ 代码

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        int n = arr.size();

        sort(arr.begin(), arr.end());

        vector<int> counter;

        int cnt = 1;
        for (int i = 1; i <= n; i++) {
            if (i == n || arr[i] != arr[i - 1]) {
                counter.push_back(cnt);
                cnt = 0;
            }
            cnt++;
        }

        sort(counter.begin(), counter.end());

        for (int i = 0; i < counter.size(); i++) {
            if (k >= counter[i]) k -= counter[i];
            else return counter.size() - i;
        }

        return 0;
    }
};