LC347　前 K 个高频元素¶

中等通过率 66%python3核心代码模式堆样例通过牛客 AC数组哈希表分治桶排序计数快速选择排序堆（优先队列）

牛客原题　源码

讲解章节：优先队列与堆

一句话

先统计词频，再用一个大小为 k 的小顶堆筛出频次最高的 k 个。

解题思路¶

这题考什么¶

两个独立的子问题。第一步统计每个值出现了几次，用哈希表一趟扫完，O(n)。第二步是从 m 个不同的值里挑出频次最大的 k 个——经典的 Top-K 问题。

把全部 (频次, 值) 排序再取前 k 个是 O(m log m)，题面明确要求优于 O(n log n)，排序法在 m 接近 n 时正好卡在下界上，不满足进阶要求。

Top-K 的标准做法是维护一个容量为 k 的小顶堆（见优先队列与堆）。堆里放当前最强的 k 个候选，堆顶是这 k 个里最弱的一个：

堆还没满  -> 直接压入；
堆已满    -> 新候选的频次若大于堆顶，说明它比现任最弱者更强，
             弹掉堆顶换它进来；否则连堆里最弱的都比不过，直接丢弃。

「求前 K 大用小顶堆」初看反直觉，理由是：需要被淘汰的永远是当前 k 个里最小的那个，而小顶堆的堆顶恰好就是最小值，O(1) 就能拿到、O(log k) 就能换掉。换成大顶堆，堆顶是最强的那个，反倒找不到该淘汰谁，只能全遍历一遍。

堆里存的是元组 (频次, 值)。Python 的元组按字典序比较，第一维就是频次，正好符合「按频次排序」的需要；第二维只在频次相同时参与比较，题面保证答案集合唯一，所以它取什么值都不影响最终结果。

值域只有 [-1e4, 1e4] 时也可以按「桶排序」做：开一个下标为频次的桶数组，从高频往低频收集，能到严格 O(n)。堆的写法不依赖值域，是更通用的模板。

数据规模与复杂度¶

1 <= nums.length <= 1e5，-1e4 <= nums[i] <= 1e4， k 在 [1, 不同元素的个数] 之内，题面保证答案集合唯一。统计 O(n)；筛选阶段每个不同的值至多做一次 O(log k) 的堆操作，合计 O(m log k)，m 为不同元素个数。k <= m <= n，所以总复杂度 O(n + m log k)，严格优于 O(n log n)，满足进阶要求。空间 O(m)：计数表加一个至多 k 个元素的堆。

坑在哪¶

判题按 unordered 比对（meta.json 的 judge 已配好，不要改）。依据是题面原文「你可以按 任意顺序 返回答案」—— 前 k 个高频元素是个集合，集合本身唯一（题面保证），但排列方式不唯一，所以只放宽顺序，不放宽内容：少一个、多一个、换一个都仍然判错。
求前 K 大要用小顶堆，不是大顶堆。堆顶必须是「当前候选里最弱的」，才能 O(1) 找到淘汰对象。用大顶堆会变成每次都要扫全堆找最小值。
堆的容量恒定为 k，不能把所有元素都压进去。全压进去再弹 k 次，复杂度是 O(m log m)，与排序同阶，进阶要求就白提了。
比较必须是「大于堆顶才替换」。写成大于等于会在频次相同时做无谓的替换，虽然本题答案集合唯一、结果不受影响，但多出的堆操作纯属浪费。
别把频次和值的位置放反。元组按字典序比较，(频次, 值) 是按频次排序，写成 (值, 频次) 就变成按值排序，答案会彻底跑偏。
题面保证 k 不超过不同元素的个数，所以不必处理「k 太大」的情况；但也不要反过来假设 k 一定小于某个常数。
最后返回的是值，不是频次。从堆里的元组取第二维，取错就成了出现次数。

样例复核¶

nums = [1, 1, 1, 2, 2, 3]，k = 2。统计：{1: 3, 2: 2, 3: 1}。遍历（顺序取决于字典的插入序，这里是 1、2、3）：

(3, 1) 堆未满 -> 压入，堆 = [(3, 1)]
(2, 2) 堆未满 -> 压入，堆 = [(2, 2), (3, 1)]，堆顶是最弱的 (2, 2)
(1, 3) 堆已满，频次 1 不大于堆顶频次 2 -> 丢弃

取出值：{1, 2}。期望 [1, 2]，本解按堆的内部顺序给出的是 [2, 1]——集合相同、顺序不同， unordered 比对判通过，这正是该题配置宽松比对的原因。

参考实现¶

solutions/leetcode/LC347/sol.py
import heapq
from typing import List, Optional


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 第一步：一趟扫描统计词频，O(n)。字典的键是值、值是出现次数
        counter = {}
        for x in nums:
            counter[x] = counter.get(x, 0) + 1
        # 第二步：容量恒为 k 的**小顶堆**，堆里放当前最强的 k 个候选。
        # 求前 K 大却用小顶堆，是因为要淘汰的永远是候选里最弱的那个，
        # 而小顶堆的堆顶恰好就是它，O(1) 可取、O(log k) 可换。
        # 元素是元组 (频次, 值)：元组按字典序比较，第一维正是排序依据，
        # 位置放反成 (值, 频次) 就变成按值排序，答案会跑偏
        heap = []
        for value, freq in counter.items():
            if len(heap) < k:
                # 堆还没装满，来者不拒
                heapq.heappush(heap, (freq, value))
            elif freq > heap[0][0]:
                # 堆已满：新候选强过现任最弱者才值得替换。
                # heappushpop 把「压入 + 弹出最小」合成一次堆调整，比分两步快。
                # 用严格大于而非大于等于，避免频次相同时做无谓的替换
                heapq.heappushpop(heap, (freq, value))
            # 频次不超过堆顶的直接丢弃：连当前最弱的候选都比不过，
            # 后面也不会有机会翻身，堆容量因此始终不超过 k
        # 返回的是**值**（元组第二维），不是频次。
        # 题面允许任意顺序，堆的内部排列不必再整理
        return [item[1] for item in heap]

LC347 前 K 个高频元素¶