LeetCode 347：最高频的 K 个元素

很重点的一道题，是剑指Offer，LeetCode里面常见的另一道题：返回数组里最小/大的K个元素进阶版。

同时也是海量数据处理课里讲过的一道基础题，后序还有各种进阶的在线解法。

自己有思路但因为语法不够熟练，参考了讨论区的解法写的程序：涉及到了很多C++基础知识，值得好好复习。

C++ STL 优先队列的应用

缺点：最后是倒序输出的。

class Solution { public://using value_t = pair<int, int>; //不要忘记等号typedef pair<int, int> value_t;// 因为堆中元素不是标准的数据类型 && 要用最小堆，需要定义struct cmp {bool operator() (const value_t& a, const value_t& b) {return a.second > b.second;}}; //结构体定义的分号不可少!!!vector<int> topKFrequent(vector<int>& nums, int k) {int n = nums.size();vector<int> ret;if(nums.empty()) return ret; //1-将数组转换成哈希表unordered_map<int, int> dict;for (auto num : nums) {dict[num] ++;}//2-将哈希表存入最小堆中，将多余的元素弹出，留下的最后k项就是最高频的k项//using value_t pair<int, int>;priority_queue<value_t, vector<value_t>, cmp> pq;for (auto a : dict) {pq.push(a);if(pq.size() > k) {pq.pop();}}//3-将堆中元素保存到数组中返回,但这样是倒序输出的while(!pq.empty()) {ret.push_back(pq.top().first);pq.pop();}return ret;} };

 最大堆：最后是正序输出的，与最小堆的性能对比见末尾。

class Solution { public://using value_t = pair<int, int>; //不要忘记等号typedef pair<int, int> value_t;// 因为堆中元素不是标准的数据类型 && 要用最小堆，需要定义struct cmp {bool operator() (const value_t& a, const value_t& b) {return a.second < b.second;}}; //结构体定义的分号不可少!!!vector<int> topKFrequent(vector<int>& nums, int k) {int n = nums.size();vector<int> ret;if(nums.empty()) return ret; //1-将数组转换成哈希表unordered_map<int, int> dict;for (auto num : nums) {dict[num] ++;}//2-将哈希表存入最大堆中//using value_t pair<int, int>;priority_queue<value_t, vector<value_t>, cmp> pq;for (auto a : dict) {pq.push(a);}//3-将堆中元素保存到数组中返回,但这样的倒序输出的for(int i=0; i<k; i++) {ret.push_back(pq.top().first);pq.pop();}return ret;} };

效率对比：

改用最大堆，最后结果是按照频率逐高到低排序的，但是建堆的时间复杂度O(n)，空间也是O(n)，取k个元素是O(klogn)，

时间O(n) + O(n) + O(klogn)，空间也是O(n)。

用最小堆时间复杂度：遍历建哈希表O(n) + 维护一个大小为k的堆O(nlogk)，空间复杂度最坏O(n) + O(k)。

总结

以上是生活随笔为你收集整理的LeetCode 347：最高频的 K 个元素的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。