跳到主要内容

LeetCode 347. 前 K 个高频元素

本节目标

先用哈希表压缩为频率记录，再用固定容量堆筛选最重要的 k 个候选。

这道题是堆与优先队列解题框架的第二道母题。它把哈希计数与 Top K 筛选连接起来：先提取每个元素的频率，再让堆只保留频率最高的 k 个候选。

查看原题

题意与约束​

给定整数数组 nums 和整数 k，返回出现频率最高的 k 个元素。题目保证答案唯一，返回顺序可以任意。

例如 nums = [1, 1, 1, 2, 2, 3]、k = 2。三个不同元素的频率分别是 3、2、1，所以答案包含 1 和 2。

先把原问题压缩成候选记录​

堆无法仅凭原数组中的单个元素知道它的总频率。第一步应使用哈希表统计：

元素值 -> 出现次数

统计完成后，长度为 n 的原数组被压缩成至多 m 条记录，其中 m 是不同元素的数量。接下来处理的候选不再是单独的数，而是：

(频率, 元素值)

比较优先级时以频率为主，元素值只是随记录一起保存，以便最终返回。

用小根堆维护最高频的 K 个​

遍历所有频率记录，将每条记录加入小根堆。如果堆大小超过 k，就弹出当前频率最低的记录。

循环不变量是：处理完若干条频率记录后，堆中保存这些记录里频率最高的至多 k 条。最终堆中的元素就是答案集合。

这里仍然是“求最大的 k 个，却使用小根堆”：因为堆顶代表当前候选中最弱的一项，新候选更强时，它最先被淘汰。

为什么答案顺序不固定​

优先队列只保证堆顶是最小频率记录，不保证堆内其余元素按频率完整有序；哈希表的遍历顺序也没有统一保证。因此，两份实现返回的答案顺序可能不同。

题目明确允许任意顺序，所以不需要为展示顺序额外排序。判断正确性时应把答案视为集合，而不是要求固定排列。

代码实现​

C++ 使用 unordered_map 统计频率，并把 (频率, 元素值) 放入小根堆；Python 使用 dict 与 heapq 完成相同过程。源码中的比较依据都是频率。

C++17
#include <functional>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> frequency;
        for (int value : nums) {
            frequency[value]++;
        }

        using Entry = pair<int, int>;
        priority_queue<Entry, vector<Entry>, greater<Entry>> top;
        for (const auto& [value, count] : frequency) {
            top.push({count, value});
            if (static_cast<int>(top.size()) > k) {
                top.pop();
            }
        }

        vector<int> answer;
        while (!top.empty()) {
            answer.push_back(top.top().second);
            top.pop();
        }
        return answer;
    }
};

复杂度分析​

设数组长度为 n，不同元素数量为 m。

  • 时间复杂度：O(n + m log k)。统计频率需要 O(n)，每条不同元素记录最多进行一次插入和一次删除。
  • 空间复杂度：O(m + k)。频率表保存 m 条记录，堆最多保存 k 条记录。

因为 m ≤ n，也可以把最坏时间写成 O(n log k)，空间写成 O(n)。

易错点​

  • 直接把元素值放入堆，得到的是数值最大的元素，而不是频率最高的元素。
  • 每遇到一次元素就更新堆，既难维护旧频率记录，又会产生大量重复候选；应先完成频率统计。
  • 误以为堆中元素天然按频率排序，从而依赖不受保证的返回次序。
  • 忘记限制堆大小，退化为保存全部不同元素。

模式迁移​

这道题展示了常见的两阶段结构：

  1. 用哈希表把原始数据转换成统计记录；
  2. 用堆从记录中筛选 Top K。

当题目改成“最常见的单词”“贡献最高的用户”或“距离最小的 K 个点”时，只需替换候选记录及比较规则，固定容量堆的主体不变。如果题目还规定同频率下的字典序，就需要把次关键字也纳入比较规则。