前 K 个高频元素 图解题解

这道题真正在问什么

给一个整数数组和数字 k，返回出现频率前 k 高的那些元素，顺序不限。它天然拆成两步：先数清每个数出现几次，再从这些频次里挑出最大的 k 个。第一步用哈希表数频次毫无悬念；这道题真正考的是第二步——「选前 k 大」怎么做得比全排序更聪明。

为什么不该把频次全排序

把所有（值，频次）按频次排序再取前 k 当然正确，但要 O(n log n)。浪费在哪？排序给出了全体元素的完整次序，而我们只关心「谁能进前 k」，前 k 之外的元素彼此谁大谁小根本无所谓。关键观察：只需要动态维护一个「目前最强的 k 个」的小圈子，新元素来了就和圈里最弱的比一比，更强就把最弱的踢出去。这个「随时找到圈内最弱者」的需求，正是堆的主场。

为什么用最小堆而不是最大堆

直觉常会反着走：求前 k 大不是该用最大堆吗？用最大堆得把全部元素建堆再连弹 k 次，堆的规模是 n。换成只装 k 个元素的最小堆，堆顶永远是圈子里频次最低的那个——恰好是随时要淘汰的对象：新元素入堆，一旦超过 k 个就弹掉堆顶，弱者出局、强者留下，堆始终只有 k 的规模。

两个容易翻车的点：一是堆的比较键必须是频次而不是数值本身，所以入堆的是（频次，值）这样的二元组；二是必须先用哈希表把频次统计完再入堆，直接把原数组元素怼进堆会把同一个值拆成多份，频次全错。

凭什么留在堆里的就是前 k 高

循环全程保持一个不变量：堆里装的始终是「到目前为止频次最高的至多 k 个元素」。每次被弹出的都是当前堆中频次最小的，它已经输给了堆里所有同伴；又因为频次在入堆之前就统计完毕、不会再变化，被淘汰者永远没有翻盘机会。所以全部元素处理完后，堆里剩下的 k 个就是全局频次前 k 高，正确性不依赖任何输入顺序。

复杂度多少，能做到 O(n) 吗

数组长度为 n 时，哈希表里的不同元素至多 n 个，每个各做一次入堆、至多一次弹出，每次 O(log k)，总时间 O(n log k)；空间 O(n+k)，哈希表存频次、堆只存 k 个。k 远小于 n 时比全排序省得多。

想彻底去掉 log 可以换桶排序：频次的取值范围只能是 1 到 n，开 n+1 个桶，把每个元素放进「下标等于它频次」的桶里，再从高频桶往低频桶倒着收集，凑满 k 个就停，整体 O(n)。面试先给堆解、再补一句桶排序的优化，是这道题的完整答案。

Python

import heapq
from collections import Counter
def topKFrequent(nums, k):
    cnt = Counter(nums)          # 1) 数频次
    heap = []                    # 最小堆：(频次, 值)
    for val, fr in cnt.items():
        heapq.heappush(heap, (fr, val))
        if len(heap) > k:        # 超员
            heapq.heappop(heap)  # 弹掉频次最小的
    return [val for fr, val in heap]

C++

vector<int> topKFrequent(vector<int>& nums, int k){
    unordered_map<int,int> cnt;
    for(int x : nums) cnt[x]++;            // 1) 数频次
    // 最小堆：pair<频次, 值>
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    for(auto& [val, fr] : cnt){
        pq.push({fr, val});
        if((int)pq.size() > k) pq.pop();   // 弹掉频次最小的
    }
    vector<int> ans;
    while(!pq.empty()){ ans.push_back(pq.top().second); pq.pop(); }
    return ans;
}

Java

public int[] topKFrequent(int[] nums, int k){
    Map<Integer,Integer> cnt = new HashMap<>();
    for(int x : nums) cnt.merge(x, 1, Integer::sum);  // 1) 数频次
    // 最小堆：按频次升序，堆顶=频次最小
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for(Map.Entry<Integer,Integer> e : cnt.entrySet()){
        pq.offer(new int[]{e.getKey(), e.getValue()});
        if(pq.size() > k) pq.poll();      // 弹掉频次最小的
    }
    int[] ans = new int[k];
    for(int i = 0; i < k; i++) ans[i] = pq.poll()[0];
    return ans;
}