LeetCode 347. 前K个高频元素——桶排序O(n)与堆O(nlogk)的工程选择
LeetCode 347. 前K个高频元素——桶排序O(n)与堆O(nlogk)的工程选择
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等
开篇故事
这道题是 215「第K大元素」的频率统计版——不是找数值最大的K个，而是找出现频率最高的K个。
有意思的地方在于，这道题有一个 O(n) 的解法，比最优的堆解法 O(n log k) 还快，而且这个 O(n) 解法用的是最基础的「桶排序」思想，不需要任何复杂数据结构。
在工程中，我见过很多人遇到「前K高频」就无脑上堆，其实有时候桶排序是更简洁、更快的选择。今天就把两种解法的工程权衡讲清楚。
一、题目解析
题目描述：
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。
要求： 算法的时间复杂度必须优于 O(n log n)。
示例：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
输入：nums = [1], k = 1
输出：[1]二、解法一：全排序
思路分析
统计频率 → 按频率排序 → 取前K个。
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 统计频率
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.merge(num, 1, Integer::sum);
}
// 按频率降序排序
List<Integer> keys = new ArrayList<>(freqMap.keySet());
keys.sort((a, b) -> freqMap.get(b) - freqMap.get(a));
// 取前K个
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = keys.get(i);
}
return result;
}
}复杂度分析
- 时间复杂度：O(n log n)。统计 O(n)，排序 O(m log m)（m 是不同元素数，最坏 m=n）。
- 空间复杂度：O(n)。
三、解法二：最小堆维护前K高频
思路分析
统计完频率后，用最小堆维护频率最高的 K 个元素。
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 统计频率
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.merge(num, 1, Integer::sum);
}
// 最小堆，按频率排序，维护前K高频
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
(a, b) -> freqMap.get(a) - freqMap.get(b)
);
for (int num : freqMap.keySet()) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
// 收集结果
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = minHeap.poll();
}
return result;
}
}复杂度分析
- 时间复杂度：O(n log k)。统计 O(n)，堆操作 O(m log k)。
- 空间复杂度：O(n + k)。
四、解法三（最优）：桶排序 O(n)
核心思想
频率的范围是 [1, n]（n 是数组长度）。创建 n+1 个「桶」，下标表示频率，每个桶里存有这个频率的元素。
然后从频率最高的桶开始（下标从大到小），收集前 K 个元素。
完整代码
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int n = nums.length;
// 第一步：统计频率
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.merge(num, 1, Integer::sum);
}
// 第二步：建桶（桶的下标 = 频率）
// bucket[i] 存所有出现次数为 i 的元素
List<Integer>[] bucket = new List[n + 1];
for (int i = 0; i <= n; i++) {
bucket[i] = new ArrayList<>();
}
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
int freq = entry.getValue();
bucket[freq].add(entry.getKey());
}
// 第三步：从高频桶向低频桶扫，收集前K个
int[] result = new int[k];
int idx = 0;
for (int freq = n; freq >= 1 && idx < k; freq--) {
for (int num : bucket[freq]) {
result[idx++] = num;
if (idx == k) break;
}
}
return result;
}
}复杂度分析
- 时间复杂度：O(n)。统计 O(n)，建桶 O(m)，扫桶 O(n)，整体 O(n)。
- 空间复杂度：O(n)。桶数组大小 n+1。
五、两种解法的工程选择
| 维度 | 桶排序 O(n) | 最小堆 O(n log k) |
|---|---|---|
| 时间 | O(n) | O(n log k) |
| 空间 | O(n)（桶数组 = 元素值域大小） | O(n + k) |
| 适用场景 | 频率范围小（1~n），静态批量 | 流式数据，频率范围大 |
| 代码复杂度 | 简单 | 简单 |
| 稳定性 | 稳定 | 不稳定（堆的顺序不保证） |
结论： 对于 LeetCode 这道题，桶排序更优。但如果是工程中「日志分析的高频词」这种场景，元素值域无限大，桶排序不可行，用堆。
六、踩坑实录
坑一：桶数组的初始化
bucket 是 List<Integer>[] 类型，Java 不允许直接创建泛型数组，但可以用 new List[n+1] 然后逐一初始化：
List<Integer>[] bucket = new List[n + 1]; // 注意：不是 new List<Integer>[n+1]
for (int i = 0; i <= n; i++) {
bucket[i] = new ArrayList<>(); // 手动初始化每个桶
}如果忘记初始化就直接 bucket[freq].add(num)，会产生 NPE。
坑二：堆解法中 Comparator 引用了 freqMap
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
(a, b) -> freqMap.get(a) - freqMap.get(b)
);这里的 lambda 引用了 freqMap，是 effectively final 的。但如果你在后面修改了 freqMap（比如在同一个方法中用于其他目的），堆的比较结果就会乱。本题没有这个问题，但要养成习惯。
坑三：result 数组的顺序
题目说「返回出现频率前K高的元素，顺序不重要」。但很多同学会写出按频率降序排的结果，然后发现答案不被接受（实际上题目要求不限顺序）。
七、总结
347 是一道把「频率统计 + TopK」结合的经典题。
桶排序给出了 O(n) 的优秀解法，充分利用了「频率值域有限（1~n）」这个约束。当值域有界时，优先考虑桶排序；值域无限时，用堆。
这个「有界值域 → 桶排序，无限值域 → 堆」的决策框架，在很多实际工程场景中都能发挥作用。