347. 前 K 个高频元素

难度：🟡 Medium | 标签：堆、哈希、桶排序 | 状态：⬜ LeetCode 链接

思路

1. 哈希统计频次
2. 小顶堆按频次维护前 K
3. 输出堆里所有元素

代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int x : nums) cnt[x]++;
        auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
            return a.second > b.second;     // 小顶堆按 freq
        };
        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
        for (auto& p : cnt) {
            pq.push(p);
            if ((int)pq.size() > k) pq.pop();
        }
        vector<int> res;
        while (!pq.empty()) { res.push_back(pq.top().first); pq.pop(); }
        return res;
    }
};

复杂度

• 时间 O(n log k)，空间 O(n)

易错 / 回顾

• 比较器方向：> 是小顶堆
• 桶排序解法 O(n)：用 vector<vector<int>>(n+1) 按频次分桶
• 返回顺序题目不要求，堆 pop 顺序即可