题目描述
给一非空的单词列表,返回前 k 个出现频率最高的单词。
要求:
- 频率高的单词排在前面;
- 若多个单词频率相同,按字典序升序排列;
- 保证答案唯一,且
1 ≤ k ≤ 单词列表中不同单词的数量。
示例 1:
输入:words = ["i","love","leetcode","i","love","coding"], k = 2
输出:["i","love"]
解释:"i" 和 "love" 分别出现 2 次,"i" 字典序小于 "love",故排在前。
示例 2:
输入:words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
输出:["the","is","sunny","day"]
解释:频率排序:the (4) > is (3) > sunny (2) > day (1),频率相同无冲突,按顺序返回前 4 个。
解法思路
解法一:哈希表 + 自定义排序
1. 思路分析
- 统计频率:用哈希表统计每个单词的出现次数;
- 自定义排序:对哈希表的键值对排序,排序规则为:
- 优先按频率降序(频率高的在前);
- 频率相同时按单词字典序升序(字典序小的在前);
- 截取结果:取排序后前
k个单词作为答案。
2. 完整代码(带详细注释)
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
# 统计每个单词的出现频率
dictword = {}
for word in words:
# get 方法简化计数:存在则取当前值 +1,不存在则默认 0+1
dictword[word] = dictword.get(word, 0) + 1
# 自定义排序:
# key=lambda x: (-x[1], x[0])
# -x[1]:按频率降序(负号实现降序);x[0]:频率相同时按单词字典序升序
dictword_sorted = sorted(dictword.items(), key=lambda x: (-x[], x[]))
res = []
key, val dictword_sorted[:k]:
res.append(key)
res

