前 K 个高频元素

最直接的想法：用哈希表数出每个数的次数，再把所有数按次数从大到小排序，取前 k 个。能对，但我们只要前 k 个，却把每个数都排得明明白白，多花了 log n 的排序，浪费。

转折：一个数最多出现 n 次，所以「次数」的取值只有 0~n 这有限几种。开一排桶，桶下标 = 出现次数，把每个数丢进「它次数对应的桶」。再从下标最大(次数最高)的桶往回扫，凑够 k 个就停——这样避开了对全部元素的整体排序，整体只 O(n)。

数次数 · 扫一遍累加(进行中)：第一步先扫一遍数组数次数：见一个加一个，哈希表查改都是 O(1)。扫到这里，前三个 1 已让 cnt[1]=3，刚遇到第一个 2，cnt[2]=1。

数次数 · 扫完(完成态)：数组扫完，得到每个数的次数：1→3、2→2、3→1。计数阶段就这么直白——纯 O(n) 累加。这张表就是下一步装桶的原料。

装桶(进行中) · 1 先进「下标3」桶：第二步装桶。注意画面下半区已经从哈希表换成了「桶阵列」——桶下标就是出现次数。先把 1 丢进它次数对应的「下标3的桶」。2、3 还没放。

装桶 · 2 进「下标2」桶、3 进「下标1」桶：接着把 2 丢进「下标2的桶」、3 丢进「下标1的桶」。装桶完成。桶是按次数分的，次数再大也超不过 n，所以桶的数量有限——这正是能用桶排序的根。

取 Top K · 从下标最大的桶倒着扫：第三步从下标最大(次数最高)的桶往回扫。先看「下标3的桶」，里面是 1，收走，res=[1]，已有 1 个，还差 1 个凑够 k=2。

取 Top K · 再扫「下标2」桶 · 凑够 → 停：倒到「下标2的桶」，取出 2，res=[1,2]，凑够 k=2 个，立刻停。看「下标1的桶」标了 ✗未碰——低频的 3 压根没被扫到。这就是比整体排序省的地方：整体排序要把 3 也排进去，桶法直接跳过。答案 [1, 2]。

Top K 高频的通杀思路：先哈希计数，再拿「次数」当桶下标。只要某个量(次数、分数、年龄)取值范围有限，桶排序就能避开 O(n log n) 的整体排序。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。