資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告