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

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

題解：

一、思路：

1.我希望將nums中的元素按照它們的出現次數從大到小排序。這樣輸出排序后的前K個元素就好；

2.如何得知nums中每個元素出現的次數呢？使用map哈希表。unordered_map<int,int>，key為nums中的元素，value為該元素出現的次數；

3.如何排序呢？考慮使用頂堆。大頂堆還是小頂堆呢？應該使用小頂堆。小頂堆中只維護K個元素，當新來的元素比隊尾的元素還大時，彈出隊頭的元素，在隊尾放入新的元素；

4.最后輸出小頂堆中所有的key。

二、代碼實現：

1.創建哈希表：

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;
}

說明：map[nums[i]]++這句會執行將key為nums[i]的value進行++操作。如果沒有nums[i]的key，則會先創建一個<nums[i],0>，再對value進行++操作；

2.創建小頂堆：

priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size > k) pri_que.pop();
}

說明：

(1)

priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;

以上代碼中：pair<int,int>為pri_que中的數據類型；vector<pair<int,int>>為pri_que的底層數據結構；mycompare為pri_que的比較器類。由于是小頂堆，mycompare比較器類定義如下：

class mycompare {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};

(2)

for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size > k) pri_que.pop();
}

unordered_map<int,int>::iterator it = map.begin()意味創建迭代器it作為循環變量；

3.取出頂堆中所有的元素：

vector<int>result;
for (int i = k - 1; i >= 0; i--) {result.push_back(pri_que.top().first);pri_que.pop();
}
return result;

完成代碼：

class Solution {class mycompare {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map;for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size > k) pri_que.pop();}vector<int>result;for (int i = k - 1; i >= 0; i--) {result.push_back(pri_que.top().first);pri_que.pop();}return result;}
};