题目描述
思路解析
一句话答案：LeetCode 1481 不同整数的最少数目：删掉恰好 k 个元素让剩下种类最少，按出现次数从小到大删——删一类的代价就是它的频次，先端低频掉得最快，时间 O(n log n)。
删恰好 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)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「先灭最弱的种类」:同样花预算 k，干掉出现次数少的数字最划算，种类数掉得最快。
第一拍:扫到第 0 个元素 4(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
第二拍:频次表新增一行 4:1(高亮行)。
第一拍:扫到第 1 个元素 3(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
第二拍:频次表新增一行 3:1(高亮行)。
第一拍:扫到第 2 个元素 1(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
第二拍:频次表新增一行 1:1(高亮行)。
第一拍:扫到第 3 个元素 1(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。
第二拍:把 1 的次数更新到 2(高亮行)。
第一拍:扫到第 4 个元素 3(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。
第二拍:把 3 的次数更新到 2(高亮行)。
第一拍:扫到第 5 个元素 3(紫色)。先看频次表里有没有它:已经有了，待会儿次数 +1。
第二拍:把 3 的次数更新到 3(高亮行)。
第一拍:扫到第 6 个元素 2(紫色)。先看频次表里有没有它:没有，待会儿新建一行。
第二拍:频次表新增一行 2:1(高亮行)。
全部扫完，频次表成型:4→1、3→3、1→2、2→1，一共 4 种数字。接下来只关心这些「次数」，元素本身不再重要。
现在舞台上的每个格子是一个「种类的出现次数」，已从小到大排好:[1, 1, 2, 3]。最左边是最容易被整类删掉的种类。
看第 0 个种类:它出现 1 次。手里还有 k=3 次删除额度，够不够把这 1 个全删光?
k ≥ 1，把这一整类删干净:预算扣掉 1 变成 k=2，不同种类数减到 3。这一格记为已清空(绿色一下，随后灰掉)。
看第 1 个种类:它出现 1 次。手里还有 k=2 次删除额度，够不够把这 1 个全删光?
k ≥ 1，把这一整类删干净:预算扣掉 1 变成 k=1，不同种类数减到 2。这一格记为已清空(绿色一下，随后灰掉)。
看第 2 个种类:它出现 2 次。手里还有 k=1 次删除额度，够不够把这 2 个全删光?
k=1 已经小于 2，删不动这一整类了(红色)。剩下的 1 个额度只能从某一类里删掉一部分，删不光就不会让种类减少，所以计数到此为止。剩下的种类数就是答案。
收尾:左边 2 个低频种类被整类删掉(灰)，耗掉 2 个额度;还剩的 1 个额度从某个高频类里删掉一部分(删不光、种类不减)，正好凑满删 3 个。绿色这 2 个高频种类还在。答案 = 2。
边界:删空得 0、k=0 原样、删不光一整类则种类不减。
两个高频追问:O(n) 桶排优化 + 反向贪心的对照。
参考代码
from typing import Listfrom collections import Counterclass 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复杂度
- 时间：O(n log n)，统计 O(n)，对至多 n 个频次排序 O(n log n)
- 空间：O(n)，哈希表与频次数组最多存 n 个不同数字
易错点
面试追问把动画讲成自己的话
追问能不能不排序，做到 O(n)?
追问如果要求删除后不同整数「最多」，思路要怎么变?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最少的后缀翻转次数
LeetCode 1529 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题