LeetCode 1481. 不同整数的最少数目（计数+排序+贪心）

示例 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

class Solution {	//C++
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
    	unordered_map<int,int> m;
    	int i;
    	for(i = 0; i < arr.size(); ++i)
    		m[arr[i]]++;
    	vector<int> count(m.size());
    	i = 0;
    	for(auto it = m.begin(); it != m.end(); ++it)
    		count[i++] = it->second;
    	sort(count.begin(), count.end());
    	i = 0;
    	while(k > 0)
    	{
    		k -= count[i];
    		if(k >= 0)
    			i++;
    	}
    	return count.size()-i;
    }
};

class Solution:# py3
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        d = {}
        for i in arr:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
        count = list(d.values())
        # count.sort()
        count = sorted(count)
        i = 0
        for c in count:
            k -= c
            if k >= 0:
                i += 1
            if k <= 0:
                break
        return len(count) - i