力扣 1481. 不同整数的最少数目

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

示例 1：

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

输入：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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/least-number-of-unique-integers-after-k-removals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1. 先统计各个数字出现的次数，然后按照数量从小到大排序，优先删除数量小的数，直到移除了给定的数量，最后计算还剩下的数字种类。

class Solution {
public:
    static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
}
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {

        map<int,int> statistic;

        for(auto i:arr)
        {
            statistic[i]++;
        }

        vector<pair<int,int>> s(statistic.begin(),statistic.end());

        sort(s.begin(),s.end(),cmp);

        int del = 0;
        int total = s.size();
        for(auto n:s)
        {
            k -= n.second;
            if(k>=0) del++;
            else break;
        }
        return total - del;

    }
};