数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中Top K高频词
假设我们有一个非空的单词列表；我们需要找到出现频率最高的k个单词。我们的答案应该按频率从高到低排序。当两个单词具有相同的频率时，字母顺序较小的单词将放在前面。例如，如果数组是[‘the’, ‘sky’, ‘is’, ‘blue’, ‘the’, ‘weather’, ‘is’, ‘comfortable’]，则出现频率最高的单词是["is","the","blue"]。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个名为m的map
- 创建一个名为v的优先队列
- 对于i := 0到n，其中n是单词数组的大小，则将m[words[i]]加1
- 对于map中的每个元素e
- 如果v的大小< k，则将e插入v
- 否则，如果v.top的值< e的值，则从v中删除顶部元素并将e插入v。
- 否则，如果v.top的值= e的值并且v.top的键> e的键，则从v中删除顶部元素，并将e插入v
- 定义一个名为res的数组
- 当v不为空时
- temp := v的顶部元素
- 从v中删除顶部元素
- 将temp的键插入res数组
- 反转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"]
更新于：2020年4月29日
498 次浏览
广告