给一非空的单词列表,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。 输入:第1行为k值,第2行单词列表,单词列表以end结尾,end不属于单词列表中的单词。 2 i love leetcode i love coding end 输出: i love
时间: 2024-02-05 18:12:00 浏览: 17
这是一道经典的Top K 问题,我们可以使用哈希表和堆来解决。首先遍历单词列表,使用哈希表记录每个单词出现的次数。然后将哈希表中的键值对转化为元组,并将元组存储到一个列表中。接下来,我们可以使用堆来找到出现次数最多的前 k 个单词。堆可以在 O(nlogk) 的时间内完成这个操作。最后,按照题目要求进行排序,输出前 k 个单词即可。
下面是代码实现:
```python
import heapq
from collections import defaultdict
def topKFrequent(words, k):
counter = defaultdict(int)
for word in words:
counter[word] += 1
heap = []
for key, value in counter.items():
heap.append((-value, key))
heapq.heapify(heap)
result = []
for i in range(k):
result.append(heapq.heappop(heap)[1])
return result
# 测试代码
words = []
while True:
word = input()
if word == "end":
break
words.append(word)
k = int(input())
result = topKFrequent(words, k)
result.sort()
print('\n'.join(result))
```
输入样例:
```
2
i love
leetcode
i
love
coding
end
```
输出样例:
```
i
love
```