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

这道题到底在问什么

输入

arr=[5,5,4], k=1

输出

1 （删掉 4，只剩 5）

输入

arr=[4,3,1,1,3,3,2], k=3

输出

2 （优先删低频:删 4 删 2，剩 1 和 3 两种）

最优解：一步一步想明白

1. 3记住「先灭最弱的种类」:同样花预算 k，干掉出现次数少的数字最划算，种类数掉得最快。
2. 4第一拍:扫到第 0 个元素 4(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
3. 5第二拍:频次表新增一行 4:1(高亮行)。
4. 6第一拍:扫到第 1 个元素 3(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
5. 7第二拍:频次表新增一行 3:1(高亮行)。
6. 8第一拍:扫到第 2 个元素 1(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
7. 9第二拍:频次表新增一行 1:1(高亮行)。
8. 10第一拍:扫到第 3 个元素 1(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。
9. 11第二拍:把 1 的次数更新到 2(高亮行)。
10. 12第一拍:扫到第 4 个元素 3(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。
11. 13第二拍:把 3 的次数更新到 2(高亮行)。
12. 14第一拍:扫到第 5 个元素 3(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。
13. 15第二拍:把 3 的次数更新到 3(高亮行)。
14. 16第一拍:扫到第 6 个元素 2(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
15. 17第二拍:频次表新增一行 2:1(高亮行)。
16. 18全部扫完，频次表成型:4→1、3→3、1→2、2→1，一共 4 种数字。接下来只关心这些「次数」，元素本身不再重要。
17. 19现在舞台上的每个格子是一个「种类的出现次数」，已从小到大排好:[1, 1, 2, 3]。最左边是最容易被整类删掉的种类。
18. 20看第 0 个种类:它出现 1 次。手里还有 k=3 次删除额度，够不够把这 1 个全删光?
19. 21k ≥ 1，把这一整类删干净:预算扣掉 1 变成 k=2，不同种类数减到 3。这一格记为已清空(绿色一下，随后灰掉)。
20. 22看第 1 个种类:它出现 1 次。手里还有 k=2 次删除额度，够不够把这 1 个全删光?
21. 23k ≥ 1，把这一整类删干净:预算扣掉 1 变成 k=1，不同种类数减到 2。这一格记为已清空(绿色一下，随后灰掉)。
22. 24看第 2 个种类:它出现 2 次。手里还有 k=1 次删除额度，够不够把这 2 个全删光?
23. 25k=1 已经小于 2，删不动这一整类了(红色)。剩下的 1 个额度只能从某一类里删掉一部分，删不光就不会让种类减少，所以计数到此为止。剩下的种类数就是答案。
24. 26收尾:左边 2 个低频种类被整类删掉(灰)，耗掉 2 个额度;还剩的 1 个额度从某个高频类里删掉一部分(删不光、种类不减)，正好凑满删 3 个。绿色这 2 个高频种类还在。答案 = 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问