// 小頂堆

? ? class mycomparison {

? ? 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> map; // map<nums[i],對應出現的次數>

? ? ? ? for (int i = 0; i < nums.size(); i++) {

? ? ? ? ? ? map[nums[i]]++;

? ? ? ? }

?

? ? ? ? // 對頻率排序

? ? ? ? // 定義一個小頂堆，大小為k

? ? ? ? priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

?

? ? ? ? // 用固定大小為k的小頂堆，掃面所有頻率的數值

? ? ? ? for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {

? ? ? ? ? ? pri_que.push(*it);

? ? ? ? ? ? if (pri_que.size() > k) { // 如果堆的大小大于了K，則隊列彈出，保證堆的大小一直為k

? ? ? ? ? ? ? ? pri_que.pop();

? ? ? ? ? ? }

? ? ? ? }

?

? ? ? ? // 找出前K個高頻元素，因為小頂堆先彈出的是最小的，所以倒序來輸出到數組

? ? ? ? vector<int> result(k);

? ? ? ? for (int i = k - 1; i >= 0; i--) {

? ? ? ? ? ? result[i] = pri_que.top().first;

? ? ? ? ? ? pri_que.pop();

? ? ? ? }

? ? ? ? return result;

?

? ? }

?

?

?