C ++中排名前K的常用词
假设我们有一个非空的单词列表；我们必须找到k个最频繁的元素。我们的答案应该按照频率从高到低的顺序排序。当两个单词具有相同的频率时，则将首先按字母顺序排列较低的单词。因此，如果数组像['the'，'sky'，'is'，'blue'，'the'，'weather'，'is'，'comfortable']一样，则最常用的单词是[“is”，“the”，“blue”]
为了解决这个问题，我们将遵循以下步骤-
定义一张称为m的映射
创建一个优先级队列v
对于i：=0到n，其中n是单词数组的大小，然后将m[words[i]]加1
对于映射中的每个元素e
如果v<k的大小，则将e插入v
否则，如果v.top的值<e的值，则从v中删除top元素并将e插入v。
否则，如果v.top的值为=e的值并且v.top的键为>e的键，则从v中删除top元素，将e插入v
定义一个称为res的数组
当v不为空时，
temp：=v的顶部
从v删除top
将临时键插入res数组
反转res数组
返回资源
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Comparator{
bool operator()(pair <string ,int> a, pair <string, int> b){
if(a.second != b.second) return !(a.second < b.second);
return !(a.first > b.first);
}
};
class Solution {
public:
static bool cmp(pair <string, int> a, pair <string, int> b){
if(a.second != b.second) return a.second > b.second;;
return a.first < b.first;
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m;
priority_queue < pair <string, int>, vector < pair <string, int> >, Comparator > v;
for(int i = 0; i < words.size(); i++){
m[words[i]]++;
}
map<string, int> :: iterator i = m.begin();
while(i != m.end()){
if(v.size() < k){
v.push(*i);
}
else if(v.top().second < i->second){
v.pop();
v.push(*i);
}
else if(v.top().second == i->second && v.top().first > i->first){
v.pop();
v.push(*i);
}
i++;
}
vector <string> res;
while(!v.empty()){
pair <string, int> temp = v.top();
v.pop();
res.push_back(temp.first);
}
reverse(res.begin(), res.end());
return res;
}
};
main(){
Solution ob;
vector<string> v = {"the", "sky", "is", "blue", "the", "weather", "is", "comfortable"};
print_vector(ob.topKFrequent(v, 3));
}输入项
["the", "sky", "is", "blue", "the", "weather", "is", "comfortable"] 3
输出结果
["is","the","blue"]