给一非空的单词列表,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
时间: 2024-02-20 07:59:53 浏览: 20
好的,这道题可以使用哈希表和堆来解决。具体思路如下:
1. 遍历单词列表,统计每个单词出现的次数,记录到哈希表中。
2. 将哈希表中的每个键值对(单词和出现次数)插入到一个大小为k的小根堆中,堆中存储的是出现次数最多的k个单词。
3. 遍历完单词列表后,堆中剩余的就是出现次数最多的k个单词,按照题目要求输出即可。
具体实现可以参考以下C++代码:
```c++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
struct WordFreq {
string word;
int freq;
WordFreq(string w, int f) : word(w), freq(f) {}
bool operator<(const WordFreq& 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> freqMap;
for (string word : words) {
freqMap[word]++;
}
priority_queue<WordFreq> pq;
for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
pq.push(WordFreq(it->first, it->second));
if (pq.size() > k) {
pq.pop();
}
}
vector<string> result;
while (!pq.empty()) {
result.insert(result.begin(), pq.top().word);
pq.pop();
}
return result;
}
int main() {
vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
int k = 2;
vector<string> result = topKFrequent(words, k);
for (string word : result) {
cout << word << " ";
}
// 输出 "i love"
return 0;
}
```
这里定义了一个结构体`WordFreq`,用于存储单词和出现次数。在结构体中,重载了小于运算符,使得在堆中按照出现次数和字母顺序来排序。
在`topKFrequent`函数中,遍历单词列表,统计每个单词出现次数,然后将它们插入到大小为k的小根堆中。在插入时,如果堆的大小超过了k,就将堆中的最小元素弹出。
最后,将堆中的元素按照出现次数和字母顺序从大到小排序,将它们存储到一个vector中,返回即可。