LeetCode：347. 前 K 个高频元素
给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。
这道题第一眼，是典型的topK问题，第一想法就是堆，所以选择先用哈希表记录每个数出现的次数，再放进堆里找前K个
struct cmp{ bool operator()(pair<int,int>a,pair<int,int>b){ return a.second<b.second; } }; class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int>ump; vector<int>ans; for(auto c:nums){ ump[c]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>q; for(auto c:ump){ q.push(c); } while(k--){ ans.push_back(q.top().first); q.pop(); } return ans; } };这是我写的第一版代码，时间复杂度是nlogn，首先要手写比较器，增加代码的复杂度，而且建堆和维护都可以优化，从而优化时间复杂度
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int>ump; vector<int>ans; for(auto c:nums){ ump[c]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; for(auto [key,value]:ump){ q.push({value,key}); if(q.size()>k)q.pop(); } while(!q.empty()){ ans.push_back(q.top().second); q.pop(); } return ans; } };这是第二版代码，只维护一个小跟堆，并且只维护K的大小的堆，少了很多维护堆的消耗，也让时间复杂度优化到nlogk
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int>ump; int max_cnt=0; for(auto c:nums){ ump[c]++; max_cnt=max(max_cnt,ump[c]); } vector<vector<int>>bucket(max_cnt+1); for(auto [x,c]:ump){ bucket[c].push_back(x); } vector<int>ans; for(int i=max_cnt;ans.size()<k;i--){ ans.insert(ans.end(),bucket[i].begin(),bucket[i].end()); } return ans; } };最后这个代码是使用桶排序，通过出现次数来分桶，相同出现次数会被分到一个桶，当ans.size()等于k的时候就会跳出结束，桶排序将时间复杂度降低到n，是这道题的最优解