哈希算法题目：前 K 个高频元素

题目描述

给定一个整数数组 nums 和一个整数 k，请返回数组中出现频率前 k 高的元素。可以按任意顺序返回答案。
示例：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
解释：1 出现 3 次，2 出现 2 次，3 出现 1 次，频率前 2 高的元素是 1 和 2。

解题过程

步骤 1：理解问题核心

• 我们需要统计每个元素出现的频率（次数）。
• 然后找出频率最高的 k 个元素。
• 本质上是一个“统计 + 排序/选择”问题，哈希表非常适合用于频率统计。

步骤 2：频率统计（哈希表的基本使用）

• 使用哈希表（字典/HashMap）来记录每个数字出现的次数。
• 键（key）：数组中的数字。
• 值（value）：该数字出现的次数。
• 遍历数组，对每个数字：
  • 如果它不在哈希表中，插入并设置次数为 1。
  • 如果已存在，将其次数加 1。

示例的执行过程（nums = [1,1,1,2,2,3]）：

初始哈希表：{}
遇到 1 → 哈希表：{1:1}
遇到 1 → 哈希表：{1:2}
遇到 1 → 哈希表：{1:3}
遇到 2 → 哈希表：{1:3, 2:1}
遇到 2 → 哈希表：{1:3, 2:2}
遇到 3 → 哈希表：{1:3, 2:2, 3:1}

此时我们得到了频率统计：{1:3, 2:2, 3:1}。

步骤 3：从频率中找出前 k 高的元素

现在我们有了每个数字的频率，需要找出频率最高的 k 个数字。
常见的方法有：

1. 排序法：将哈希表中的所有键值对按值（频率）从大到小排序，取前 k 个键。

   • 时间复杂度：统计 O(n)，排序 O(m log m)（m 是不同数字的个数，最坏 m = n）。
   • 空间复杂度：O(m) 存储哈希表。

2. 堆（优先队列）法：维护一个大小为 k 的最小堆，堆顶是当前堆中频率最小的元素。遍历哈希表，将每个元素尝试加入堆，如果堆大小超过 k 则弹出堆顶（最小频率元素），这样遍历完后堆中剩下的就是频率最高的 k 个元素。

   • 时间复杂度：统计 O(n)，建堆 O(m log k)，当 k ≪ m 时比排序法更优。
   • 空间复杂度：O(m) 哈希表 + O(k) 堆。

这里我们以堆法为例详细讲解，因为它更高效且是常见考点。

步骤 4：使用最小堆找出 Top K

最小堆（min-heap）的特性是堆顶元素最小。我们想保留频率最大的 k 个元素，可以在堆中存储（频率, 数字）对，并按频率排序。每次比较新元素和堆顶的频率：

• 如果堆大小 < k，直接插入。
• 如果堆大小 = k，且新元素的频率 > 堆顶频率，则弹出堆顶，插入新元素。
• 最终堆中剩下的就是频率最大的 k 个元素。

示例的堆操作过程（k=2）：
哈希表：{1:3, 2:2, 3:1}

1. 插入 (3,1) → 堆：[(3,1)]
2. 插入 (2,2) → 堆大小 < k，插入 → 堆：[(2,2), (3,1)]（堆顶是频率 2）
3. 插入 (1,3) → 堆大小 = k，新频率 1 ≤ 堆顶频率 2，不插入。
   最终堆中元素：[(2,2), (3,1)] → 对应的数字是 [2,1]（顺序任意）。

步骤 5：算法实现（伪代码/关键步骤）

1. 统计频率：

   freq_map = {}
   for num in nums:
       freq_map[num] = freq_map.get(num, 0) + 1
   

2. 用最小堆找 Top K：

   min_heap = []  # 存储 (频率, 数字)
   for num, freq in freq_map.items():
       将 (freq, num) 入堆
       if 堆大小 > k:
           弹出堆顶
   

3. 从堆中提取结果：

   result = []
   while 堆不为空:
       弹出堆顶 (freq, num)
       result.append(num)
   return result
   

注意：由于是最小堆，弹出的顺序是频率从小到大的，所以最终结果可能是逆序的。但这不影响答案，因为题目允许任意顺序。

步骤 6：复杂度分析

• 时间复杂度：O(n + m log k)，其中 n 是数组长度，m 是不同数字的个数（m ≤ n）。统计频率 O(n)，堆操作 O(m log k)。
• 空间复杂度：O(m) 用于哈希表，O(k) 用于堆，总体 O(m)。

步骤 7：扩展思考

• 如果 k 接近 m，排序法可能更简单直接。
• 还有一种“桶排序”思路：创建一个数组，索引表示频率，值是该频率对应的数字列表（频率不超过 n）。然后从高频率向低频率遍历，收集 k 个数字。时间复杂度 O(n)，但需要 O(n) 额外空间。

总结

这个题目结合了哈希表（快速统计频率）和堆（高效选择 Top K）两种数据结构，是处理“频率前 K”问题的典型方法。关键在于：

1. 先用哈希表统计频率。
2. 再用大小为 k 的最小堆筛选出频率最高的 k 个元素。