不同整数的最少数目 图解题解

删恰好 k 个后，剩几种数字最少

给一个整数数组 arr 和整数 k，删掉恰好 k 个元素，返回剩下的数字里最少能有几种不同的值。要点是删一个数字的某类必须把这类全删光，种类数才减一——只要还剩一个，这种数字就仍然算存在。题面例子 arr=[5,5,4]、k 为 1，删掉那个单独的 4，只剩 5 这一种，答案 1；再看 arr=[4,3,1,1,3,3,2]、k 为 3，答案 2。

为什么不能见一个删一个

删哪 k 个才让种类最少，直接枚举所有删法会炸：从 n 个元素里挑 k 个删，组合数是天文数字，规模一大就跑不动。就算只盯种类，一个想当然的删法是先动出现最多的那类、把最扎眼的数字清掉——可高频类往往有一大把，预算全砸进去也未必删得光，删了半截种类根本不减，纯属白花。

删一类的代价，就是它的频次

把每类删光的代价摆出来就清楚了：删掉某一种数字让种类减一，要花的预算恰好等于它出现的次数。想用同样的 k 把种类压到最低，预算就该花在代价最小的类上，也就是出现次数最少的那些种类。于是每步都端掉当前预算够得着、频次最小的一类，这种每步都盯住最小频次、拿最少预算换一次种类减少的选法就是贪心。按频次从小到大一路删，能删几类种类就减几；高频类先留着，用它们去扛最后那点删不光的零头。

统计、升序、够就删三步

落到代码就三步。先用哈希表（Python 的 Counter、C++ 的 unordered_map、Java 的 HashMap）扫一遍数组，数出每种数字出现几次；再把这些频次值单独取出来，从小到大排序；然后拿 k 当预算从最小的频次开始扣：当前频次 c 若满足 k≥c，就把 k 减去 c、种类数减一，接着看下一类；一旦 k＜c，这类删不光了，立刻停，此刻剩下的种类数就是答案。remain 从种类总数起步，删一类扣一个，最后返回它。

arr=[4,3,1,1,3,3,2]、k 为 3 走一遍

先统计频次：4 出现 1 次、3 出现 3 次、1 出现 2 次、2 出现 1 次，一共 4 种，remain 记 4。把频次排成升序 [1,1,2,3]。第一格 c=1，预算 k 还有 3、够删，删光这一类，k 降到 2、remain 减到 3。第二格 c=1，k 还剩 2、再删光，k 降到 1、remain 减到 2。第三格 c=2，k 只剩 1、比 2 小，这一类删不光，停。此刻 remain 是 2 就是答案：耗掉的 2 个预算删净了两类低频，剩下 1 个预算只能从高频类里抠掉一个、删不光不减种类，正好凑满删 3 个。

删法容易错在哪，复杂度多少

有三处容易删错。删的方向反了、从高频开刀，同样的预算换来的种类减少更少，答案会偏大。把一类删掉一半也当种类减少，可只要还剩一个这数字就在，种类不变，半删白花预算。忘了 k 可能一个整类都删不动，这时不该硬凑，直接返回当前种类数即可。

复杂度上，统计频次是 O(n)，对至多 n 个频次排序是 O(n log n)，合起来 O(n log n)；哈希表和频次数组最多存 n 个不同数字，空间 O(n)。

Python

from typing import List
from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = sorted(Counter(arr).values())
        remain = len(freq)
        for c in freq:
            if k >= c:
                k -= c
                remain -= 1
            else:
                break
        return remain

C++

#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int,int> count;
        for (int x : arr) count[x]++;
        vector<int> freq;
        for (auto &p : count) freq.push_back(p.second);
        sort(freq.begin(), freq.end());
        int remain = freq.size();
        for (int c : freq) {
            if (k >= c) { k -= c; remain--; }
            else break;
        }
        return remain;
    }
};

Java

import java.util.*;
class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
        List<Integer> freq = new ArrayList<>(count.values());
        Collections.sort(freq);
        int remain = freq.size();
        for (int c : freq) {
            if (k >= c) { k -= c; remain--; }
            else break;
        }
        return remain;
    }
}