给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。这道题第一眼是典型的topK问题第一想法就是堆所以选择先用哈希表记录每个数出现的次数再放进堆里找前K个struct cmp{ bool operator()(pairint,inta,pairint,intb){ return a.secondb.second; } }; class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,intump; vectorintans; for(auto c:nums){ ump[c]; } priority_queuepairint,int,vectorpairint,int,cmpq; for(auto c:ump){ q.push(c); } while(k--){ ans.push_back(q.top().first); q.pop(); } return ans; } };这是我写的第一版代码时间复杂度是nlogn首先要手写比较器增加代码的复杂度而且建堆和维护都可以优化从而优化时间复杂度class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,intump; vectorintans; for(auto c:nums){ ump[c]; } priority_queuepairint,int,vectorpairint,int,greaterpairint,intq; 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的大小的堆少了很多维护堆的消耗也让时间复杂度优化到nlogkclass Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,intump; int max_cnt0; for(auto c:nums){ ump[c]; max_cntmax(max_cnt,ump[c]); } vectorvectorintbucket(max_cnt1); for(auto [x,c]:ump){ bucket[c].push_back(x); } vectorintans; for(int imax_cnt;ans.size()k;i--){ ans.insert(ans.end(),bucket[i].begin(),bucket[i].end()); } return ans; } };最后这个代码是使用桶排序通过出现次数来分桶相同出现次数会被分到一个桶当ans.size()等于k的时候就会跳出结束桶排序将时间复杂度降低到n是这道题的最优解