給你一個整數數組?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;}
};