给一非空的单词列表,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。 输入:第1行为k值,第2行单词列表,单词列表以end结尾,end不属于单词列表中的单词。 2 i love leetcode i love coding end 输出: i love
时间: 2024-02-05 17:13:47 浏览: 28
这道题可以使用哈希表来统计每个单词出现的次数,然后再按照出现次数和字母顺序排序。具体实现如下:
```python
import heapq
from collections import Counter
# 输入
k = int(input())
words = []
while True:
word = input().strip()
if word == "end":
break
words.append(word)
# 统计每个单词出现的次数
counter = Counter(words)
# 使用堆来保存出现次数最多的k个单词
heap = []
for word, count in counter.items():
heapq.heappush(heap, (-count, word))
# 输出前k个出现次数最多的单词
for i in range(k):
count, word = heapq.heappop(heap)
print(word)
```
这里使用了Python的 `Counter` 类来统计每个单词出现的次数,并使用了Python的 `heapq` 模块来实现小根堆。由于Python的堆默认是小根堆,而题目要求按照出现次数从大到小排序,因此需要将出现次数取负数再加入堆中。同时,由于堆默认按照元素大小排序,而我们要求按照出现次数和字母顺序排序,因此需要在元素中同时保存出现次数和单词本身,以便在出现次数相同时按照字母顺序排序。
相关问题
给一非空的单词列表,返回前k个出现次数最多的单词林大oj
题目描述
给一非空的单词列表,返回前k个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
示例
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 "i" 在 "love" 之前。
说明
假定k总为有效值,1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。
解题思路
首先要统计每个单词出现的次数,可以使用哈希表来完成。然后根据出现次数和字母顺序排序,可以使用优先队列来完成。
具体地,将字符串和其出现次数存储到哈希表中,然后将哈希表中的每个元素都加入到优先队列中,队列中元素按照以下规则排序:
- 如果出现次数不同,根据出现次数排序,出现次数多的在前面。
- 如果出现次数相同,根据字母顺序排序,字母靠前的在前面。
最后取出队列前k个元素的字符串即可。
时间复杂度:O(nlogk)。其中n是输入列表的长度,哈希表和优先队列的插入操作的时间复杂度均为O(logk),总共需要插入n个元素。
空间复杂度:O(n)。哈希表存储n个单词,优先队列存储k个单词。
参考代码
给一非空的单词列表,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
好的,这道题可以使用哈希表和堆来解决。具体思路如下:
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中,返回即可。