LeetCode K个高频元素：桶排序算法与关键细节解析

本文深入探讨了“k个高频元素”问题的桶排序解法。通过使用哈希映射统计元素频率，并利用数组作为桶（索引为频率，存储对应频率的元素列表），该方法能高效找出前k个出现频率最高的元素。文章着重分析了在填充桶时遍历哈希映射的键集（`keyset()`）而非原始数组的重要性，以确保桶中元素唯一性，避免结果错误。

在算法设计中，高效地从一组数据中找出出现频率最高的K个元素是一个常见且重要的任务。LeetCode上的“K个高频元素”问题正是对此类场景的典型考量。本文将详细介绍一种基于哈希映射（HashMap）和桶排序（Bucket Sort）的解决方案，并特别强调在实现过程中一个关键的细节——如何正确地填充桶。

算法核心思想

解决“K个高频元素”问题通常可以分为两个主要阶段：

1. 频率统计： 首先，我们需要遍历输入数组 nums，统计每个数字出现的频率。这可以通过使用一个哈希映射（HashMap）来实现，其中键是数组中的数字，值是该数字出现的次数。
2. 桶排序与结果收集： 接下来，我们创建一个“桶”结构，通常是一个 List[] 数组。这个数组的索引代表元素的频率，而每个索引处存储的 List 则包含所有具有该频率的数字。例如，bucket[2] 将存储所有出现频率为2的数字。由于我们希望找到频率最高的K个元素，我们可以从桶数组的末尾（即最高频率）开始向前遍历，依次收集元素，直到收集到K个为止。

频率统计阶段

这一阶段相对直观。我们初始化一个 HashMap，然后遍历输入数组 nums。对于 nums 中的每一个数字 n，我们更新其在 map 中的频率。如果 n 首次出现，其频率初始化为1；否则，在原有频率上加1。

// the frequency of each element stored in map. 
var map = new HashMap(); 
for(int n : nums) {
    map.put(n, map.getOrDefault(n, 0) + 1); 
}

桶排序阶段：填充桶的关键细节

在频率统计完成后，我们需要将这些数字根据它们的频率放入对应的桶中。这一步是整个算法中一个容易出错但至关重要的环节。

桶的定义如下：List[] bucket = new ArrayList[nums.length + 1];。这里的 nums.length + 1 是因为频率的最大值可能等于 nums.length（当所有元素都相同时），所以需要一个足够大的数组来容纳所有可能的频率作为索引。

现在，问题来了：我们应该遍历 nums 数组还是 map.keySet() 来填充桶？

为什么必须遍历 map.keySet()

正确的做法是遍历 map.keySet()。map.keySet() 返回的是哈希映射中所有唯一的键（即输入数组中所有不重复的数字）。对于每一个唯一的数字 n，我们获取其在 map 中对应的频率 freq，然后将 n 添加到 bucket[freq] 对应的列表中。

// 正确的填充桶方式
for(int n : map.keySet()) { // 遍历唯一的数字
    int freq = map.get(n);
    if(bucket[freq] == null) {
        bucket[freq] = new ArrayList(); 
    }
    bucket[freq].add(n); 
}

原因分析： 桶 bucket[freq] 应该存储的是“所有出现频率为 freq 的唯一数字”。题目要求返回的是K个不同的高频元素。如果 bucket[freq] 中包含了重复的数字，那么在后续收集结果时，我们会错误地将同一个数字多次计入结果，或者导致最终结果包含非去重元素，从而不符合题目要求。

map.keySet() 保证了我们每次处理的都是一个唯一的数字。例如，如果输入是 [1, 1, 2, 2, 3]，map 会是 {1:2, 2:2, 3:1}。遍历 map.keySet() 时，我们会依次处理 1、2、3。

来福FM

来福 - 你的私人AI电台

下载

• 对于 1 (freq=2)，bucket[2] 中添加 1。
• 对于 2 (freq=2)，bucket[2] 中添加 2。
• 对于 3 (freq=1)，bucket[1] 中添加 3。 最终 bucket[2] 包含 [1, 2]，bucket[1] 包含 [3]，完美符合预期。

为什么不能遍历 nums 数组

如果尝试遍历原始的 nums 数组来填充桶，将会导致错误的结果：

// 错误的填充桶方式
for(int n : nums) { // 遍历原始数组，可能包含重复数字
    int freq = map.get(n);
    if(bucket[freq] == null) {
        bucket[freq] = new ArrayList(); 
    }
    bucket[freq].add(n); 
}

错误分析： 继续使用 [1, 1, 2, 2, 3] 的例子。

• 第一次遇到 1 (freq=2)，bucket[2] 中添加 1。
• 第二次遇到 1 (freq=2)，bucket[2] 中再次添加 1。
• 第一次遇到 2 (freq=2)，bucket[2] 中添加 2。
• 第二次遇到 2 (freq=2)，bucket[2] 中再次添加 2。
• 遇到 3 (freq=1)，bucket[1] 中添加 3。 最终 bucket[2] 可能会变成 [1, 1, 2, 2]。当我们在收集结果时，如果 k=2，我们从 bucket[2] 中取出 1 和 1，这显然是错误的，因为 1 应该只被计作一个不同的高频元素。bucket 中的每个 List 应该只包含唯一的数字。

完整代码示例

结合上述分析，以下是“K个高频元素”问题的完整Java解决方案：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 频率统计：使用HashMap统计每个数字的出现频率
        Map map = new HashMap<>(); 
        for(int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1); 
        }

        // 2. 桶排序：创建一个List数组作为桶，索引代表频率
        // 桶的长度为 nums.length + 1，因为最大频率可能等于 nums.length
        List[] bucket = new ArrayList[nums.length + 1]; 

        // 3. 填充桶：遍历map的keySet()，将唯一的数字根据其频率放入对应的桶中
        // 这一步是关键，确保桶中存储的是唯一的数字
        for(int n : map.keySet()) {
            int freq = map.get(n);
            if(bucket[freq] == null) {
                bucket[freq] = new ArrayList<>(); 
            }
            bucket[freq].add(n); 
        }

        // 4. 收集结果：从频率最高的桶开始逆序遍历，收集前K个元素
        int[] result = new int[k];
        int resultIndex = 0; // 用于填充结果数组的索引

        // 从最高频率（bucket.length - 1）开始向下遍历
        for(int i = bucket.length - 1; i >= 0; i--) {
            if(bucket[i] != null) { // 如果当前频率的桶不为空
                for(int element : bucket[i]) { // 遍历桶中的每个元素
                    result[resultIndex++] = element;
                    if(resultIndex == k) { // 如果已收集到K个元素，则返回
                        return result; 
                    }
                }
            }
        }

        return result; // 理论上不会执行到这里，因为题目保证K是有效的
    }
}

注意事项与总结

1. 时间复杂度：

   • 频率统计（HashMap）：遍历 nums 数组一次，O(N)，其中 N 是 nums 的长度。
   • 填充桶：遍历 map.keySet()，最多有 N 个不同的元素，每次操作 O(1)，所以也是 O(N)。
   • 结果收集：最坏情况下，可能需要遍历所有桶和所有元素才能找到 K 个，但每个元素只会被访问一次，所以也是 O(N)。
   • 综合时间复杂度为 O(N)。

2. 空间复杂度：

   • HashMap：最坏情况下，所有元素都不同，存储 N 个键值对，O(N)。
   • bucket 数组：存储 N 个列表，所有元素也都在列表中，O(N)。
   • 综合空间复杂度为 O(N)。

3. 桶中元素唯一性： 再次强调，在填充桶时，必须遍历 HashMap 的键集 (map.keySet())，以确保每个桶中存储的都是唯一的数字。这是避免结果错误的关键。

4. 适用场景： 桶排序方法在处理频率范围相对较小（与元素数量N大致相同）的问题时表现优秀。如果频率范围极大，桶数组会非常稀疏，可能造成空间浪费，但对于 LeetCode 的这类问题，通常频率范围在 [0, N] 之间，因此是高效的选择。

通过理解并正确应用哈希映射和桶排序的原理，特别是对填充桶这一关键步骤的细致处理，我们可以高效且准确地解决“K个高频元素”这类问题。