给一非空的单词列表,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。 输入:第1行为k值,第2行单词列表,单词列表以end结尾,end不属于单词列表中的单词。 2 i love leetcode i love coding end 输出: i love
时间: 2024-02-11 16:10:02 浏览: 109
以下是一个实现,使用了一个最大堆来维护前k个出现次数最多的单词:
```
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
struct Word {
string word;
int freq;
bool operator<(const Word& other) const {
if (freq == other.freq) {
return word < other.word;
}
return freq > other.freq;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> freq;
for (string& word : words) {
freq[word]++;
}
priority_queue<Word> maxHeap;
for (auto& pair : freq) {
maxHeap.push({pair.first, pair.second});
}
vector<Word> result;
for (int i = 0; i < k && !maxHeap.empty(); i++) {
result.push_back(maxHeap.top());
maxHeap.pop();
}
vector<string> ans;
for (auto it = result.rbegin(); it != result.rend(); it++) {
ans.push_back(it->word);
}
return ans;
}
int main() {
int k;
cin >> k;
vector<string> words;
string word;
while (cin >> word && word != "end") {
words.push_back(word);
}
vector<string> ans = topKFrequent(words, k);
for (string& word : ans) {
cout << word << endl;
}
return 0;
}
```
这个实现和之前的实现有一些差别,主要是使用了一个最大堆来维护前k个出现次数最多的单词,同时在比较单词的时候,如果出现次数相同,则按字母顺序排序。在最后输出结果之前,还需要将结果翻转一下,并提取出单词部分即可。