题目描述
给一非空的单词列表，返回前 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[1], x[0]))
# 截取前 k 个单词，组装结果列表
res = []
for key, val in dictword_sorted[:k]:
res.append(key)
return res
3. 代码核心解析
（1）频率统计
words = ["i","love","leetcode","i","love","coding"]
遍历后 dictword = {"i":2, "love":2, "leetcode":1, "coding":1}。
（2）自定义排序
sorted(dictword.items(), key=lambda x: (-x[1], x[0]))
dictword.items()：将字典转为元组列表 [("i",2), ("love",2), ("leetcode",1), ("coding",1)]；
key=lambda x: (-x[1], x[0])：
-x[1]：对频率（x[1]）取负，实现降序（2 > 1）；
x[0]：频率相同时，按单词（x[0]）的字典序升序（"i" < "love"）；
排序结果：[("i",2), ("love",2), ("coding",1), ("leetcode",1)]。
（3）截取结果
取前 k=2 个元组的单词部分，得到 ["i","love"]，符合题目要求。
4. 复杂度分析
- 时间复杂度：O(nlogn)
- 统计频率：O(n)（n 为单词列表长度）；
- 排序：O(mlogm)（m 为不同单词的数量，m≤n），是时间瓶颈；
- 空间复杂度：O(n)
- 哈希表存储所有不同单词，排序需额外存储元组列表，整体为 O(n)。
5. 优缺点
- 优点：代码极简、逻辑直观，无需自定义类或掌握堆的复杂用法，新手极易上手；
- 缺点：排序需遍历所有不同单词，当 n 极大（如 $10^6$）且 k 极小时（如 k=10），效率低于堆解法。
解法二：哈希表 + 小顶堆
1. 思路分析
针对排序解法的效率问题，用小顶堆优化：仅维护 k 个元素，避免对所有单词排序，核心逻辑：
- 哈希表统计频率（同解法一）；
- 遍历哈希表，将（单词，频率）推入小顶堆，保持堆大小不超过
k（超过则弹出'最小'元素）； - 堆中剩余的
k个元素是前k高频单词，反转后得到最终结果。
2. 完整代码（带详细注释）
import heapq
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
# 统计每个单词的出现频率
mapping = {}
for word in words:
mapping[word] = mapping.get(word, 0) + 1
# 初始化小顶堆，筛选前 k 个高频单词
heap = []
for key, val in mapping.items():
# 将自定义 Node 推入堆，heapq 会按__lt__规则排序
heapq.heappush(heap, Node(key, val))
# 保持堆大小为 k，超过则弹出'最小'的元素（频率最低/同频率字典序大）
if len(heap) > k:
heapq.heappop(heap)
# 提取堆中元素并调整顺序
res = []
while len(heap) > 0:
temp = heapq.heappop(heap)
res.append(temp.key)
# 反转后得到'大→小'的正确顺序（如 [i, love]）
res.reverse()
return res
# 自定义堆节点类，实现比较逻辑
class Node:
def __init__(self, key, val):
self.key = key # 单词
self.value = val # 出现频率
# 核心：自定义小于（__lt__）规则，适配小顶堆的排序逻辑
def __lt__(self, other):
# 规则 1：频率相同 → 字典序大的单词'更小'（优先被弹出）
if self.value == other.value:
return self.key > other.key
# 规则 2：频率不同 → 频率小的单词'更小'（优先被弹出）
else:
return self.value < other.value
3. 核心解析（关键难点）
（1）自定义 Node 类的比较规则
Python 的 heapq 默认是小顶堆，需重写__lt__方法（less than）适配题目规则：
def __lt__(self, other):
return self.key > other.key if self.value == other.value else self.value < other.value
频率相同：字典序大的单词（如 "love"）被判定为'更小'，优先弹出；频率不同：频率小的单词（如 "coding"）被判定为'更小'，优先弹出。
（2）堆筛选过程（以示例 1 为例）
- 推入 ("i",2) → 堆：[Node(i,2)]（大小 1 ≤ 2）；
- 推入 ("love",2) → 堆：[Node(love,2), Node(i,2)]（大小 2 ≤ 2）；
- 推入 ("leetcode",1) → 堆大小 3>2 → 弹出堆顶（Node(leetcode,1)）；
- 推入 ("coding",1) → 堆大小 3>2 → 弹出堆顶（Node(coding,1)）；
- 最终堆内元素：[Node(love,2), Node(i,2)]，弹出后反转得到 ["i","love"]。
4. 复杂度分析
- 时间复杂度：O(nlogk)
- 统计频率：O(n)；
- 堆操作：每次 push/pop 为 O(logk)，最多执行 m 次（m≤n），整体为 O(mlogk)；
- 当 k≪n 时，O(nlogk)≪O(nlogn)，效率优势明显；
- 空间复杂度：O(n)（哈希表 + 堆，堆仅占 O(k)）。
5. 优缺点
- 优点：时间效率更高，适合大数据量、小 k 的场景；
- 缺点：代码稍复杂，需理解堆的特性和自定义比较规则。