哈希算法题目：哈希表在解决“前K个高频单词”问题中的应用

题目描述
给定一个单词列表 words 和一个整数 k，要求返回列表中出现频率最高的前 k 个单词。返回的答案应该按单词频率从高到低排序。如果不同单词有相同频率，则按字典顺序（即字母顺序）升序排列。

示例：
输入：words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出：["i", "love"]
解释：

• "i" 出现 2 次
• "love" 出现 2 次
• "leetcode" 和 "coding" 各出现 1 次
  频率最高的前 2 个单词是 ["i", "love"]。注意，同频率时按字典序，"i" 在 "love" 之前。

解题过程循序渐进讲解

步骤1：理解问题核心
我们需要做两件事：

1. 统计频率：计算每个单词出现的次数。
2. 排序与选取：按频率从高到低排序，频率相同时按字典序升序排列，然后取前 k 个。

步骤2：选择数据结构

• 哈希表（字典）：用于存储每个单词及其出现次数，这是统计频率最高效的方法（平均 O(1) 时间存取）。
• 列表：存储所有单词及其频率，用于后续排序。
• 排序算法：对列表进行自定义排序。

步骤3：统计频率
遍历单词列表，用哈希表记录每个单词的出现次数。
具体操作：
初始化一个空字典 freq_map = {}。
对每个单词 word 执行：

• 如果 word 不在 freq_map 中，则 freq_map[word] = 1。
• 否则，freq_map[word] += 1。

示例的执行过程：
words = ["i", "love", "leetcode", "i", "love", "coding"]
遍历结束后得到：
{ "i": 2, "love": 2, "leetcode": 1, "coding": 1 }

步骤4：准备排序数据
哈希表存储了键值对，但我们需要一个列表来排序。
从 freq_map 中提取所有键值对，组成列表，每个元素是 (word, frequency) 的形式。
例如：[("i", 2), ("love", 2), ("leetcode", 1), ("coding", 1)]

步骤5：自定义排序规则
题目要求：

1. 频率从高到低排序（即频率大的在前）。
2. 频率相同时，按单词字典序升序（即字母顺序小的在前，如 "i" 在 "love" 前）。

在编程中，我们可以通过自定义排序的“比较规则”来实现。
以 Python 为例，可以对列表排序，排序的 key 规则是：

• 主要比较因素：频率，但因为是降序，所以用负频率 -frequency。
• 次要比较因素：单词本身，按字母顺序升序，即直接取 word。
  所以排序 key 可以是 (-frequency, word)。

步骤6：排序并提取前 k 个
对步骤4得到的列表按上述 key 排序，然后取前 k 个元素，只保留单词部分。
示例排序后列表：
[("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)]
（注意："coding" 在 "leetcode" 前是因为频率相同时按字母顺序，"coding" 的 'c' 在 'l' 之前）
取前 k=2 个单词：["i", "love"]。

步骤7：复杂度分析

• 时间复杂度：O(n log n)，其中 n 是不同单词的数量。统计频率 O(n) 时间，排序 O(n log n) 时间占主导。
• 空间复杂度：O(n)，存储哈希表和列表。

步骤8：边界情况考虑

• 如果 k 大于不同单词的总数，则返回所有单词（排序后）。
• 如果单词列表为空，返回空列表。
• 注意大小写：题目通常假设单词是小写字母组成，但若未说明，可能需要预处理（如转为小写）或按原样区分大小写处理。

步骤9：代码实现思路（伪代码）

function topKFrequent(words, k):
    freq_map = 空字典
    for word in words:
        freq_map[word] = freq_map.get(word, 0) + 1
    
    candidates = freq_map 中所有键值对组成的列表
    对 candidates 排序，排序规则：先按频率降序，再按单词字母顺序升序
    取 candidates 的前 k 个元素的单词部分，组成列表返回

总结
这个问题展示了哈希表在“频率统计”中的基础应用，结合自定义排序规则，可以高效解决 Top K 问题。哈希表负责快速统计，排序负责顺序排列，二者结合是处理此类问题的常见模式。