class Solution { public: // 按出现次数构造小顶堆 static bool cmp(pair<int,int>& m, pair<int,int>& n) { return m.second > n.second; } vector<int> topKFrequent(vector<int>& nums, int k) { // 统计：数字 -> 出现次数 unordered_map<int,int> orders; for (auto& v : nums) { orders[v]++; } // 创建自定义小顶堆 priority_queue< pair<int,int>, vector<pair<int,int>>, decltype(&cmp) > q(cmp); // 维护出现次数最大的 k 个元素 for (auto& [num, count] : orders) { if (q.size() == k) { // 新元素频率更大，替换堆顶 if (q.top().second < count) { q.pop(); q.emplace(num, count); } } else { // 堆未满，直接加入 q.emplace(num, count); } } // 取出堆中的数字 vector<int> res; while (!q.empty()) { res.push_back(q.top().first); q.pop(); } return res; } };

总结

这题分为三步：

① 哈希表统计频率

orders[v]++;

得到：

数字 → 出现次数

② 小顶堆维护前 K 个高频元素

cmp保证：

q.top()

始终是当前堆中出现次数最少的元素。

堆满以后，如果：

q.top().second < count

说明新元素频率更高，就：

q.pop(); // 淘汰当前最小频率 q.emplace(num, count); // 加入新元素

③ 最终堆中剩下的就是前 K 个高频元素。

复杂度：统计频率是O(n)，维护堆约为O(n log k)，整体O(n log k)；堆的大小始终不超过k。