题目描述

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

思路与算法

  首先根据题意，最终要得到不同整数的最少数目，说明我们所删除的k个元素要尽可能的互不相同，也就是说优先删除出现次数最少的元素。
  根据上述思路，这里我们选择使用map来完成<数据, 出现次数>的存储。然后通过按照出现次数递增的顺序进行删除即可。但是，map的有序性是指对key的排序，显然这里我们需要做的是对于map中的value排序。

• 方法一：使用map + vector实现对value的排序。

代码

bool cmp(const pair<int, int>& A, const pair<int, int>& B){ //规定对于map元素中value的排序规则
    return A.second < B.second;   // 按照second值从小到大排序
}
class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        int n = arr.size();
        int ans = 0;
        map<int, int> M;    // 建立关于<数据, 出现次数>的映射关系
        for(int i = 0; i < n; i++){
            if(M.find(arr[i]) == M.end()){  // 第一次出现
                M[arr[i]] = 1;
                ans++;  // ans用来记录不同数据的个数
            }else   M[arr[i]]++;
        }

        vector<pair<int, int> > vec(M.begin(), M.end());    // 将map中的内容转存到vector中
        sort(vec.begin(), vec.end(), cmp);  // 对线性的vector进行排序
        for(auto it = vec.begin(); it != vec.end(); it++){
            k -= it->second;
            if(k < 0)   break;  // 如果减去所有出现的当前元素后，k<0,则当前元素减不完
            if(k == 0){
                ans--;
                break;
            }
            ans--;  //从所有不同数据中减去当前数据
            
        }
        return ans;
    }
};

• 方法二：使用map + 优先队列实现对value的排序。(思路差不多，主要熟悉熟悉优先队列的使用）

代码

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k){
        int n = arr.size();
        unordered_map<int, int> m;
        for(int i = 0; i < n; i++)	m[arr[i]]++;
      
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for(auto x : m)	pq.push({x.second, x.first});
        while(k && pq.size()) {
      	    auto t = pq.top();
      	    if(k >= t.first)	k -= t.first;
      	    else	break;
        }
        pq.pop();
    }
    return pq.size();
};

复杂度分析

• 时间复杂度：单层for循环，时间复杂度为O(n)。
• 空间复杂度：map+vector或map+priority_queue，空间复杂度为O(n)。