Priority queue 排序找前最大K个元素 类型
priority queue 实现的数据结构是红黑树,balanced binary search tree。
471. Top K Frequent Words
471. Top K Frequent Words
class Solution {
public:
/**
* @param words: an array of string
* @param k: An integer
* @return: an array of string
*/
struct cmp{
bool operator()(const pair<string, int> &a, const pair<string, int> &b){
return a.second > b.second || (a.second == b.second && a.first < b.first);
}
};
vector<string> topKFrequentWords(vector<string> &words, int k) {
// write your code here
unordered_map<string, int> mp;
for(auto s : words){
mp[s]++;
}
priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
for(auto i : mp){
pq.push({i.first, i.second});
if(pq.size() > k){
pq.pop();
}
}
vector<string> res;
while(!pq.empty()){
res.push_back(pq.top().first);
pq.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
Comments
Post a Comment