题目描述
思路解析动画文字版
记住「先数次数,再按次数从大到小删,够一半就停」，下面每帧都在套它。
第一段:从左到右扫数组，每遇到一个数值，就在「值 → 出现次数」表里给它加一。
扫到第 0 个，是数值 3。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
数值 3 的出现次数更新到 1（高亮行）。继续往后扫。
扫到第 1 个，是数值 3（绿色是它之前出现过的位置）。给它的出现次数加一。
数值 3 的出现次数更新到 2（高亮行）。继续往后扫。
扫到第 2 个，是数值 3（绿色是它之前出现过的位置）。给它的出现次数加一。
数值 3 的出现次数更新到 3（高亮行）。继续往后扫。
扫到第 3 个，是数值 3（绿色是它之前出现过的位置）。给它的出现次数加一。
数值 3 的出现次数更新到 4（高亮行）。继续往后扫。
扫到第 4 个，是数值 5。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
数值 5 的出现次数更新到 1（高亮行）。继续往后扫。
扫到第 5 个，是数值 5（绿色是它之前出现过的位置）。给它的出现次数加一。
数值 5 的出现次数更新到 2（高亮行）。继续往后扫。
扫到第 6 个，是数值 5（绿色是它之前出现过的位置）。给它的出现次数加一。
数值 5 的出现次数更新到 3（高亮行）。继续往后扫。
扫到第 7 个，是数值 2。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
数值 2 的出现次数更新到 1（高亮行）。继续往后扫。
扫到第 8 个，是数值 2（绿色是它之前出现过的位置）。给它的出现次数加一。
数值 2 的出现次数更新到 2（高亮行）。继续往后扫。
扫到第 9 个，是数值 7。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
数值 7 的出现次数更新到 1（高亮行）。继续往后扫。
第一段扫完。各数值的出现次数是 3→4，5→3，2→2，7→1。接下来第二段:把这些次数从大到小排好,逐个累加删除。
把次数从大到小排好:4 ≥ 3 ≥ 2 ≥ 1。第二段从最大的开始删,每删一种,累计删除量增加,达到 5 个就停。
当前剩下里次数最多的是数值 3（出现 4 次,绿色这些位置）。选它,这是第 1 种被删的值。
删掉数值 3 后累计删了 4 个（红色）。4×2 = 8 还 < 10，没到一半,继续删下一个次数最大的值。
当前剩下里次数最多的是数值 5（出现 3 次,绿色这些位置）。选它,这是第 2 种被删的值。
删掉数值 5 后累计删了 7 个（红色）。7×2 = 14 ≥ 10，已达到一半！选了 2 种就停。
从次数最大的往下删,删到 3、5 这 2 种时累计删了 7 个（红色），已超过一半 5。所以最少选 2 种数值。
边界先想清:全相同删 1 种、全不同删一半种。
面试重点:计数 + 按频率贪心,可进阶到桶排序 O(n)。
参考代码
from typing import Listfrom collections import Counterclass Solution: def minSetSize(self, arr: List[int]) -> int: counts = sorted(Counter(arr).values(), reverse=True) removed = 0 for i, c in enumerate(counts, 1): removed += c if removed * 2 >= len(arr): return i return 0复杂度
- 时间：O(n log n)，计数 O(n);对 k 个不同次数降序排序 O(k log k) ≤ O(n log n)
- 空间：O(n)，计数表与次数数组,最多 n 个不同值
易错点
面试追问把动画讲成自己的话
追问能不能不排序,用更快的方法？
追问这题考的核心思维是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最多可以参加的会议数目
LeetCode 1353 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题