代码随想录 栈与队列 test 7

347. 前 K 个高频元素 - 力扣（LeetCode）

首先想到哈希，用key来存元素，value来存出现次数，最后进行排序，时间复杂度约为o(nlogn)。由于只需求前k个，因此可以进行优化，利用堆来维护这k个元素，由于最终要剩下k个最大的元素，因此元素每次加入堆时，要将堆中最小元素弹出，因此要用小根堆来维护。

class Solution {
public:class MinHeapComparator {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second; // 按频率从小到大排序}
};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> hash; //哈希表for(int i = 0; i < nums.size(); i++){hash[nums[i]]++;}priority_queue<pair<int,int>, vector<pair<int,int>>, MinHeapComparator> minheap;for(auto item : hash){//将哈希表元素加入堆中minheap.push(item);if(minheap.size() > k){minheap.pop();}}vector<int> res(k);//存前k个高频元素for(int i = k-1; i >= 0; i--){//由于是小根堆，因此倒序存在res中res[i] = minheap.top().first;minheap.pop();}return res;}
};