題目描述

給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按 任意順序 返回答案。

題目分析

1. 據題意可知，我們需要先遍歷整個數組，并統計每個數字出現的次數，保存在哈希表中；
2. 對元素出現次數進行排序，由于題中要求時間復雜度必須優于O(NlogN),且數組中的元素可能都不相同的情況；
3. 因此，我們需要利用堆排序的思想進行排序，并需要一些處理：

首先建立一個小頂堆，然后開始遍歷哈希表：
當堆中的元素個數小于K時，直接插入當前元素；
當堆中元素大于等于K時，比較堆頂和當前元素的大小，如果當前元素大，則彈出堆頂元素，并插入當前元素；反之，則舍棄當前元素；
遍歷完后，堆中元素就是前K個出現頻率最多的元素和出現的次數

4. 遍歷堆，取出需要的元素，保存到容器中返回。

Code

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> its_map;for (int num : nums) {its_map[num]++;}auto cmp = [](pair<int, int>& m, pair<int, int>& n) -> bool {return m.second > n.second;};priority_queue<pair<int,int>, vector<pair<int, int>>,decltype(cmp)> que(cmp);for (auto item : its_map) {if (k == que.size()) {if (que.top().second < item.second) {que.pop();que.emplace(item.first,item.second);}} else {que.emplace(item.first,item.second);}}vector<int> ans;ans.reserve(k);while (!que.empty()) {ans.emplace_back(que.top().first);que.pop();}return ans;}
};