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

字数 2195 2025-10-26 09:00:52

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

题目描述
给你一个整数数组 nums 和一个整数 k，请你返回数组中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]

示例 2：
输入：nums = [1], k = 1
输出：[1]

解题过程

这个问题可以分解为几个清晰的步骤。我们的目标是找出出现次数最多的 k 个元素。

第一步：统计每个元素出现的频率
这是哈希算法最典型的应用场景。我们需要知道每个数字出现了多少次。

我们创建一个哈希映射（在 Python 中是字典，在 Java 中是 HashMap），其中键（key）是数组中的数字，值（value）是该数字出现的次数。
我们遍历整个数组。对于遇到的每一个数字：
- 如果这个数字已经在哈希映射中，我们将其对应的值（频率）加 1。
- 如果这个数字不在哈希映射中，我们将其加入映射，并设置初始频率为 1。

以示例 nums = [1,1,1,2,2,3], k = 2 为例：

遍历结束后，我们得到的哈希映射是：{1: 3, 2: 2, 3: 1}。
这表示数字 1 出现了 3 次，数字 2 出现了 2 次，数字 3 出现了 1 次。

第二步：根据频率找出前 k 高的元素
现在我们有了每个元素的频率，问题转化为：在一个由（元素，频率）组成的集合中，找出频率最高的 k 个元素。

有多种方法可以解决这个问题，这里我们讲解两种常见且高效的方法。

方法一：利用最小堆（优先队列）
堆是一种特殊的二叉树结构，最小堆的根节点是整个树中最小的元素。我们可以利用这个特性来维护当前频率最高的 k 个元素。

建堆：我们创建一个最小堆，这个堆将根据元素的频率进行排序（即堆顶是堆中频率最小的那个元素）。
遍历哈希映射：我们遍历第一步中得到的哈希映射里的每一个（元素，频率）对。
- 将当前这个（元素，频率）对加入到最小堆中。
- 关键操作：如果加入后，堆的大小超过了 k（即堆中元素数量 > k），我们就将堆顶（当前频率最小的那个元素）移除。
- 这样做可以保证堆中始终只保留着到目前为止遇到的频率最高的 k 个元素。那些频率低的元素在加入后很快就会被挤出去。
输出结果：当我们遍历完所有元素后，堆中剩下的 k 个元素就是整个数组中出现频率前 k 高的元素。

继续我们的例子，哈希映射为 {1: 3, 2: 2, 3: 1}，k=2：

将 (1, 3) 加入堆。堆：[ (1,3) ]，大小=1 <=2，不弹出。
将 (2, 2) 加入堆。堆：[ (1,3), (2,2) ]（假设堆顶是(2,2)），大小=2 <=2，不弹出。
将 (3, 1) 加入堆。堆：[ (1,3), (2,2), (3,1) ]，大小=3 > 2。我们需要弹出堆顶（频率最小的元素），即弹出 (3, 1)。
最终堆中剩下 [ (1,3), (2,2) ]。所以前 k 高的元素是 [1, 2]。

这种方法的时间复杂度是 O(N log k)，其中 N 是数组长度。因为建一个大小为 k 的堆，每次插入和删除的复杂度是 O(log k)，我们操作了 N 次。

方法二：桶排序思想
这种方法在特定场景下（当频率值范围可控时）效率更高，达到 O(N)。

统计频率：第一步与方法一相同，得到频率哈希映射。例如 {1: 3, 2: 2, 3: 1}。
创建“频率桶”：我们创建一个数组（列表）作为“桶”，数组的索引代表频率，数组索引位置存放的值是一个列表，这个列表包含了所有出现次数等于该索引的数字。
- 桶数组的长度至少为 max_frequency + 1（最大频率加一）。在我们的例子中，最大频率是3，所以我们需要一个长度为4的桶数组（索引从0到3）。
- 初始化一个全为空的列表的数组：bucket = [ [], [], [], [] ]。
- 遍历哈希映射，将数字放入对应的频率桶中：
  - 频率为1的数字 3 放入 bucket[1] -> [ [], [3], [], [] ]
  - 频率为2的数字 2 放入 bucket[2] -> [ [], [3], [2], [] ]
  - 频率为3的数字 1 放入 bucket[3] -> [ [], [3], [2], [1] ]
从高到低收集 k 个元素：现在，我们从桶数组的末尾（最高频率）开始，向前遍历（向低频率方向），依次将每个桶里的元素加入到结果列表中，直到结果列表中的元素数量达到 k 个。
- 从索引3开始：bucket[3] 里有 [1]，取出，结果列表为 [1]，数量=1 < 2。
- 移到索引2：bucket[2] 里有 [2]，取出，结果列表为 [1, 2]，数量=2，等于 k，停止。

这种方法的时间复杂度是 O(N)，因为统计频率和桶排序都是线性时间。它是一种非常巧妙的解法。

总结
解决“前 K 个高频元素”问题的核心路径是：

使用哈希映射统计频率。
使用一种排序策略（如最小堆或桶排序）从频率中筛选出前 k 个。

最小堆方法更通用，桶排序方法在频率分布集中时效率极高。

哈希算法题目：前 K 个高频元素题目描述给你一个整数数组 nums 和一个整数 k，请你返回数组中出现频率前 k 高的元素。你可以按任意顺序返回答案。示例 1：输入：nums = [ 1,1,1,2,2,3 ], k = 2 输出：[ 1,2 ] 示例 2：输入：nums = [ 1 ], k = 1 输出：[ 1 ] 解题过程这个问题可以分解为几个清晰的步骤。我们的目标是找出出现次数最多的 k 个元素。第一步：统计每个元素出现的频率这是哈希算法最典型的应用场景。我们需要知道每个数字出现了多少次。我们创建一个哈希映射（在 Python 中是字典，在 Java 中是 HashMap），其中键（key）是数组中的数字，值（value）是该数字出现的次数。我们遍历整个数组。对于遇到的每一个数字：如果这个数字已经在哈希映射中，我们将其对应的值（频率）加 1。如果这个数字不在哈希映射中，我们将其加入映射，并设置初始频率为 1。以示例 nums = [1,1,1,2,2,3], k = 2 为例：遍历结束后，我们得到的哈希映射是： {1: 3, 2: 2, 3: 1} 。这表示数字 1 出现了 3 次，数字 2 出现了 2 次，数字 3 出现了 1 次。第二步：根据频率找出前 k 高的元素现在我们有了每个元素的频率，问题转化为：在一个由（元素，频率）组成的集合中，找出频率最高的 k 个元素。有多种方法可以解决这个问题，这里我们讲解两种常见且高效的方法。方法一：利用最小堆（优先队列）堆是一种特殊的二叉树结构，最小堆的根节点是整个树中最小的元素。我们可以利用这个特性来维护当前频率最高的 k 个元素。建堆：我们创建一个最小堆，这个堆将根据元素的频率进行排序（即堆顶是堆中频率最小的那个元素）。遍历哈希映射：我们遍历第一步中得到的哈希映射里的每一个（元素，频率）对。将当前这个（元素，频率）对加入到最小堆中。关键操作：如果加入后，堆的大小超过了 k（即堆中元素数量 > k），我们就将堆顶（当前频率最小的那个元素）移除。这样做可以保证堆中始终只保留着到目前为止遇到的频率最高的 k 个元素。那些频率低的元素在加入后很快就会被挤出去。输出结果：当我们遍历完所有元素后，堆中剩下的 k 个元素就是整个数组中出现频率前 k 高的元素。继续我们的例子，哈希映射为 {1: 3, 2: 2, 3: 1} ， k=2 ：将 (1, 3) 加入堆。堆： [ (1,3) ] ，大小=1 <=2，不弹出。将 (2, 2) 加入堆。堆： [ (1,3), (2,2) ] （假设堆顶是 (2,2) ），大小=2 <=2，不弹出。将 (3, 1) 加入堆。堆： [ (1,3), (2,2), (3,1) ] ，大小=3 > 2。我们需要弹出堆顶（频率最小的元素），即弹出 (3, 1) 。最终堆中剩下 [ (1,3), (2,2) ] 。所以前 k 高的元素是 [1, 2] 。这种方法的时间复杂度是 O(N log k)，其中 N 是数组长度。因为建一个大小为 k 的堆，每次插入和删除的复杂度是 O(log k)，我们操作了 N 次。方法二：桶排序思想这种方法在特定场景下（当频率值范围可控时）效率更高，达到 O(N)。统计频率：第一步与方法一相同，得到频率哈希映射。例如 {1: 3, 2: 2, 3: 1} 。创建“频率桶” ：我们创建一个数组（列表）作为“桶”，数组的索引代表频率，数组索引位置存放的值是一个列表，这个列表包含了所有出现次数等于该索引的数字。桶数组的长度至少为 max_frequency + 1 （最大频率加一）。在我们的例子中，最大频率是3，所以我们需要一个长度为4的桶数组（索引从0到3）。初始化一个全为空的列表的数组： bucket = [ [], [], [], [] ] 。遍历哈希映射，将数字放入对应的频率桶中：频率为1的数字 3 放入 bucket[1] -> [ [], [3], [], [] ] 频率为2的数字 2 放入 bucket[2] -> [ [], [3], [2], [] ] 频率为3的数字 1 放入 bucket[3] -> [ [], [3], [2], [1] ] 从高到低收集 k 个元素：现在，我们从桶数组的末尾（最高频率）开始，向前遍历（向低频率方向），依次将每个桶里的元素加入到结果列表中，直到结果列表中的元素数量达到 k 个。从索引3开始： bucket[3] 里有 [1] ，取出，结果列表为 [1] ，数量=1 < 2。移到索引2： bucket[2] 里有 [2] ，取出，结果列表为 [1, 2] ，数量=2，等于 k，停止。这种方法的时间复杂度是 O(N)，因为统计频率和桶排序都是线性时间。它是一种非常巧妙的解法。总结解决“前 K 个高频元素”问题的核心路径是：使用哈希映射统计频率。使用一种排序策略（如最小堆或桶排序）从频率中筛选出前 k 个。最小堆方法更通用，桶排序方法在频率分布集中时效率极高。