【Leetcode 692.前K个高频单词】(Python3完整代码)
一、题目描述
给一非空的单词列表，返回前 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])) # 3. 截取前k个单词，组装结果列表 res = [] for key, val in dictword_sorted[:k]: res.append(key) return res3. 代码核心解析
（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 极大（如
）且 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 = [] # 弹出堆顶（此时堆内元素是“小→大”，如[love, i]） 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.value3. 核心解析（关键难点）
（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 的场景；
- 缺点：代码稍复杂，需理解堆的特性和自定义比较规则。
