LeetCode 692. 前 K 个高频单词 Python 实现

核心解析

• 频率统计：利用 get 方法简化计数逻辑，存在则取值加 1，不存在默认从 0 开始。
• 排序技巧：sorted 函数的 key 参数接收一个元组 (-frequency, word)。Python 比较元组时先比第一个元素，再比第二个。负数让频率大的排在前面，字符串本身比较即满足字典序需求。
• 复杂度：时间复杂度 O(n log n)，瓶颈在排序。当数据量极大且 k 很小时，效率不如堆优化方案。

解法二：哈希表 + 小顶堆

如果数据量非常大（比如 $10^6$ 级别），而 k 很小，全量排序就会显得浪费。这时候可以用堆来维护前 k 个元素。

思路分析

核心在于只维护大小为 k 的小顶堆。遍历所有单词频率时，将元素推入堆中，一旦堆大小超过 k，就弹出当前'最小'的元素（频率最低或同频字典序最大）。这样堆里剩下的就是我们要找的前 k 个高频词。

代码实现

import heapq
from typing import List

class Solution:
    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

    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        # 1. 统计频率
        mapping = {}
        for word in words:
            mapping[word] = mapping.get(word, 0) + 1
        
        # 2. 初始化小顶堆
        heap = []
        for key, val in mapping.items():
            heapq.heappush(heap, self.Node(key, val))
            # 保持堆大小为 k，超过则弹出'最小'的元素
            if len(heap) > k:
                heapq.heappop(heap)
        
        # 3. 提取并反转
        res = []
        while len(heap) > 0:
            temp = heapq.heappop(heap)
            res.append(temp.key)
        
        # 堆弹出顺序是小→大，需要反转得到大→小
        res.reverse()
        return res

难点说明

Python 的 heapq 默认是小顶堆。题目要求频率高在前，同频字典序小在前。但小顶堆会不断弹出'最小'的元素。为了保留我们想要的大元素，我们需要把'不想要'的元素定义为'更小'。

所以在 __lt__ 方法里做了特殊处理：

• 频率不同时，频率小的被视为'更小'，会被优先弹出。
• 频率相同时，字典序大的被视为'更小'，会被优先弹出（因为字典序小的才应该留在堆里）。

复杂度对比

• 时间复杂度：O(n log k)。统计频率 O(n)，堆操作每次 O(log k)，最多执行 m 次（m 为不同单词数）。当 k << n 时，优势明显。
• 空间复杂度：O(n)。主要用于存储哈希表和堆。

总结

两种方案各有千秋。解法一代码极简，适合中小规模数据或快速开发场景；解法二通过堆优化了时间复杂度，在处理海量数据且 k 较小时性能更优。实际面试中，能清晰讲出堆的比较逻辑通常是加分项。