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;}
};