LeetCode刷题笔记-347-前K个高频元素

题目信息

难度：Medium
题目链接：前 K 个高频元素

题目描述

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

初步思路

拿到这道题，第一反应就是「先统计频率，再找出前 K 个」。统计频率自然想到哈希表，而找前 K 个则有两个经典方向：

排序：把频率统计完后按值排序，取前 K 个。时间复杂度 O(n log n)。
堆：维护一个大小为 K 的堆，时间复杂度可以优化到 O(n log k)。

显然当 n 很大时，堆更优。而且这道题非常经典，是「TopK」问题的模板题，值得好好整理。

算法分析

方法一：小根堆（推荐）

核心思想：先用哈希表统计每个数字的出现次数，然后用一个大小为 K 的小根堆来维护当前频率最高的 K 个元素。堆顶是这 K 个里频率最小的，遇到更大的就替换掉。
技巧要点：
- 优先队列默认是大根堆，需要自定义比较器变成小根堆。
- 使用 decltype(cmp) 获取 lambda 的类型作为模板参数，但别忘了在构造函数里传入 cmp 实例，因为 lambda 没有默认构造函数。
时间复杂度：O(n log k)，其中 n 是数组长度。每次堆操作 log k。
空间复杂度：O(n)，哈希表存储频率。

方法二：桶排序

由于频率的最大值不超过数组长度 n，可以用一个数组（桶）按频率索引存储数字，然后从高频往低频收集 K 个。
时间复杂度 O(n)，空间复杂度 O(n)。虽然渐进复杂度更优，但常数较大，面试中写小根堆更稳妥。

代码实现（C++）

小根堆版本

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

        // 小根堆：频率低的优先级高（在堆顶）
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        };

        // 注意：decltype(cmp) 推导出类型后，构造函数必须传入 cmp 实例
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

        for (auto& it : mp) {
            pq.push(it);
            if (pq.size() > k) {
                pq.pop();  // 堆顶是第 K+1 小的，弹掉
            }
        }

        vector<int> res(k);
        for (int i = k - 1; i >= 0; --i) {
            res[i] = pq.top().first;
            pq.pop();
        }
        return res;
    }
};

桶排序版本

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 1. 用哈希表统计每个数字的出现频率
        unordered_map<int, int> mp;
        for (auto x : nums) {
            mp[x]++;
        }

        int n = nums.size();
        vector<int> res;
        // 2. 建立桶数组：索引表示频率，值存储出现该频率的所有数字
        // 最大频率不会超过数组长度 n，所以桶的大小可以设为 n + 1
        vector<vector<int>> bucket(n + 1);

        // 3. 按频率将数字放入对应的桶中
        for (auto& [num, cnt] : mp) {
            bucket[cnt].push_back(num);
        }

        // 4. 从高频往低频遍历桶，收集前 K 个高频元素
        for (int i = n; i >= 1 && res.size() < k; --i) {
            for (auto num : bucket[i]) {
                res.push_back(num);
                if (res.size() == k)
                    break;  // 已经收集够 K 个，提前退出
            }
        }
        return res;
    }
};

测试用例

输入	输出	说明
`nums = [1,1,1,2,2,3], k = 2`	`[1,2]`	1 出现 3 次，2 出现 2 次
`nums = [1], k = 1`	`[1]`	只有一个元素

总结与反思

这道题是非常经典的 TopK 模板题，核心思路就是「哈希表 + 堆」。在实现过程中，有几个 C++ 细节特别容易踩坑，记录一下：

decltype(cmp) 配合 lambda 使用时，构造函数必须传 cmp 实例。因为 lambda 生成的匿名类没有默认构造函数，只写 decltype(cmp) pq; 会编译报错。
优先队列的比较器语义和 sort 是反的。sort 返回 true 表示 a 排在前面；而 priority_queue 返回 true 表示 a 的优先级更低（更靠近堆底）。所以小根堆要写成 return a.second > b.second;。
最后从堆中取出结果时，注意循环边界别写错（比如写成 i >= k 就一次都不会执行了，别问我怎么知道的哈哈 😂）。

TK的小站