精通LeetCode：Top K 频繁元素问题的桶排序解决方案与常见陷阱解析

本文深入探讨了“top k 频繁元素”问题的高效解决方案，主要采用哈希映射统计元素频率，并结合桶排序思想进行元素归类。文章详细解析了如何构建频率桶，并重点澄清了在填充桶时，为何必须遍历哈希映射的键集（keyset）而非原始数组，以避免将重复元素错误地放入桶中，确保最终输出的正确性。

问题概述

“Top K 频繁元素”问题要求从一个整数数组中找出出现频率最高的 K 个元素。例如，给定数组 nums = [1,1,1,2,2,3] 和 k = 2，预期输出为 [1,2]，因为 1 出现了 3 次，2 出现了 2 次，它们是频率最高的两个元素。解决此问题通常需要两个核心步骤：首先统计每个元素的频率，然后根据频率筛选出前 K 个元素。

核心思想：频率统计与桶排序

解决此类问题的常见且高效的方法是结合使用哈希映射（HashMap）进行频率统计，以及桶排序（Bucket Sort）思想进行元素归类。

1. 频率统计：遍历输入数组 nums，使用 HashMap<Integer, Integer> 存储每个元素及其出现的频率。键为数组中的元素，值为其出现次数。
2. 桶排序：创建一个列表数组（或称“桶”），其索引代表元素的频率，而该索引处存储的列表则包含所有具有该频率的元素。例如，bucket[3] 将存储所有出现频率为 3 的元素。由于频率最大不会超过数组长度，因此桶数组的大小通常为 nums.length + 1。

完成这两个步骤后，只需从桶数组的末尾（即高频率）向前遍历，收集元素直到达到 K 个，即可得到结果。

Java实现详解

以下是基于上述思想的 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. 统计每个元素的频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int n : nums) {
            freqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
        }

        // 2. 创建频率桶
        // 桶的索引代表频率，桶内存储具有该频率的元素列表
        // 频率最大为 nums.length，所以桶大小为 nums.length + 1
        List<Integer>[] bucket = new ArrayList[nums.length + 1];

        // 3. 将元素放入对应的频率桶中
        // 遍历 freqMap 的 keySet，确保每个不重复的元素被放入桶中一次
        for (int n : freqMap.keySet()) {
            int freq = freqMap.get(n);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(n);
        }

        // 4. 从高频率向低频率遍历桶，收集前 K 个元素
        int[] result = new int[k];
        int count = 0; // 已收集的元素数量

        // 从桶的末尾（最高频率）开始遍历
        for (int i = bucket.length - 1; i >= 0; i--) {
            if (bucket[i] != null) { // 如果当前频率的桶不为空
                for (int element : bucket[i]) {
                    result[count++] = element;
                    if (count == k) { // 达到 K 个元素，返回结果
                        return result;
                    }
                }
            }
        }
        return result; // 理论上不会执行到这里，除非 k > 数组中所有不重复元素的数量
    }
}

关键细节：为何遍历 map.keySet() 而非 nums 数组

在上述解决方案中，将元素放入频率桶的关键步骤是：

        for (int n : freqMap.keySet()) { // 注意这里是 freqMap.keySet()
            int freq = freqMap.get(n);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(n);
        }

有些开发者可能会疑惑，为什么不能直接遍历原始 nums 数组来填充桶，例如：

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

22

查看详情

        // 错误的示例：遍历 nums 数组来填充桶
        for (int n : nums) { // 这里是 nums 数组
            int freq = freqMap.get(n); // 获取元素 n 的频率
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(n); // 将元素 n 添加到对应频率的桶中
        }

原因分析：

哈希映射 freqMap 的键是唯一的，它存储了数组中所有不重复的元素。当我们遍历 freqMap.keySet() 时，我们实际上是在遍历数组中所有不同的元素。对于每个不同的元素 n，我们获取其在 freqMap 中统计出的总频率 freq，然后将这个唯一的元素 n 添加到 bucket[freq] 列表中。这意味着 bucket[freq] 列表最终会包含所有频率为 freq 的不同元素。

然而，如果选择遍历原始 nums 数组，情况就不同了。nums 数组可能包含重复元素。例如，nums = [1, 1, 1, 2, 2, 3]。 当 n = 1 第一次出现时，它会被添加到 bucket[3] 中。 当 n = 1 第二次出现时，它又会被添加到 bucket[3] 中。 当 n = 1 第三次出现时，它还会被添加到 bucket[3] 中。 最终，bucket[3] 可能会变成 [1, 1, 1]。

这会导致以下问题：

1. 数据冗余：bucket[freq] 列表中包含了重复的元素，违背了桶的初衷（每个桶应该存储具有相同频率的不同元素）。
2. 结果错误：在最后遍历桶收集结果时，如果 bucket[i] 包含 [1, 1, 1]，那么 for (int element : bucket[i]) 循环会将 1 添加到结果数组三次，这显然是错误的。Top K 频繁元素要求返回的是元素本身，而不是其出现的次数的列表。我们只需要 1 这个元素一次。

因此，为了确保 bucket[freq] 列表中只包含唯一的、具有特定频率的元素，必须遍历 freqMap.keySet()。

复杂度分析

• 时间复杂度：
  • 频率统计：遍历 nums 数组一次，时间复杂度为 O(N)，其中 N 是数组长度。
  • 填充桶：遍历 freqMap.keySet() 一次，哈希映射中最多有 N 个不重复元素，时间复杂度为 O(N)。
  • 收集结果：最坏情况下需要遍历整个 bucket 数组和其中的所有元素，时间复杂度为 O(N)。
  • 总时间复杂度：O(N)。
• 空间复杂度：
  • freqMap：最坏情况下存储 N 个不重复元素，空间复杂度为 O(N)。
  • bucket：数组大小为 N+1，最坏情况下所有元素都存储在桶中，空间复杂度为 O(N)。
  • 总空间复杂度：O(N)。

注意事项与总结

1. 桶数组大小：new ArrayList[nums.length + 1] 的设计是关键，因为它确保了所有可能的频率（从 0 到 nums.length）都有对应的存储位置。
2. 空桶处理：在遍历桶收集结果时，需要检查 if (bucket[i] != null)，因为并非所有频率都会有对应的元素。
3. K值的处理：当收集到的元素数量达到 k 时，应立即返回结果，避免不必要的遍历。
4. 其他解决方案：除了桶排序，该问题也可以使用最小堆（Min-Heap）来解决。先用哈希映射统计频率，然后将频率和元素对放入大小为 K 的最小堆中。当堆满时，如果新元素的频率大于堆顶元素的频率，则弹出堆顶元素并插入新元素。这种方法的时间复杂度通常为 O(N log K)。对于 K 值较小的情况，堆的性能可能更优；对于 K 值较大或接近 N 的情况，桶排序的 O(N) 复杂度通常更具优势。

通过本文的详细解析，我们不仅掌握了“Top K 频繁元素”问题的桶排序解决方案，更重要的是理解了在构建频率桶时遍历 map.keySet() 的必要性，从而避免了常见的逻辑陷阱。

以上就是精通LeetCode：Top K 频繁元素问题的桶排序解决方案与常见陷阱解析的详细内容，更多请关注php中文网其它相关文章！