在算法面试中，"Top K"问题是一个经典题型。今天我们要深入剖析 LeetCode 第 347 题《前 K 个高频元素》，这道题不仅考察了我们对数据结构的理解，更是哈希表与堆（优先队列）配合使用的绝佳示例。
题目回顾
给定一个整数数组 nums 和一个整数 k，返回出现频率前 k 高的元素。答案可以按任意顺序返回。
示例：
- 输入：
nums = [1,1,1,2,2,3],k= 2 - 输出：
[1,2]
解题思路分析
要解决这个问题，我们需要完成两个核心步骤：
- 统计频次：遍历数组，统计每个元素出现的次数
- 找出前 K 个高频元素：从所有元素中找出频次最高的前K 个
方法一：排序法（直观但不够高效）
最直接的想法是：
- 用哈希表统计频次 -将哈希表的键值对转换为列表 -按频次降序排序
- 取前K 个元素
public int[] topKFrequent(int[] nums, int k) {
//统计频次
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
//转换为列表并排序
List<Map.Entry<Integer, Integer>> list= new ArrayList<>(freqMap.entrySet());
list.sort((a, b)-> b.getValue() - a.getValue());
//取前K个
int[] result = new int[k];
for(int i = 0; i < k; i++) {
result[i] = list.get(i).getKey();
}
return result;
}
时间复杂度： O(n log n) 空间复杂度： O(n)
虽然这个方法能解决问题，但在面试中通常不是最优解，因为我们只需要前 K 个元素，没必要对所有元素进行完整排序。
方法二：最小堆优化（推荐解法）
这里的关键洞察是：维护一个大小为 K 的最小堆。
- 堆中存储的是
(元素,频次)对 - 堆按照频次进行排序，堆顶是频次最小的元素
- 当堆的大小超过K 时，移除堆顶（频次最小的）
- 最终堆中剩下的就是频次最高的 K 个元素
为什么用最小堆而不是最大堆？
- 最小堆能让我们快速识别并移除当前频次最低的元素
- 如果用最大堆，我们需要维护所有元素，无法有效控制堆的大小
import java.util.*;
public int[] topKFrequent(int[] nums, int k) {
// 第一步：统计频次
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num,freqMap.getOrDefault(num,0) + 1);
}
//第二步：使用最小堆维护前K个高频元素
PriorityQueue<Map.Entry<Integer,Integer>> minHeap =
new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
minHeap.offer(entry);
//如果堆的大小超过k，移除频次最小的元素
if (minHeap.size() > k) {
minHeap.poll();
}
}
//第三步：提取结果
int[] result = new int[k];
for(int i = k- 1; i >=0; i--) {
result[i] = minHeap.poll().getKey();
}
return result;
}
时间复杂度： O(n log k)
空间复杂度： O(n)
方法三：桶排序（线性时间解法）
还有一个更巧妙的方法——桶排序。由于频次的最大值不会超过数组长度 n，我们可以：
- 创建 n+1 个桶（索引 0 到 n）
- 将频次为 i 的所有元素放入第 i 个桶中
- 从后往前遍历桶，收集前 K 个元素
public int[] topKFrequent(int[] nums, int k){
// 统计频次
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num,freqMap.getOrDefault(num,0) + 1);
}
//创建桶：buckets[i] 存储频次为 i 的所有元素
ArrayList<Integer>[] buckets = new ArrayList[nums.length +1];
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()){
int freq = entry.getValue();
if(buckets[freq] == null) {
buckets[freq] = new ArrayList<>();
}
buckets[freq].add(entry.getKey());
}
// 从后往前收集前K个元素
int[] result = new int[k];
int index = 0;
for (int i = buckets.length - 1; i >= 0 && index < k; i--) {
if (buckets[i] != null) {
for(int num : buckets[i]) {
result[index++] = num;
if (index == k) {
break;
}
}
}
}
return result;
}
时间复杂度： O(n)
空间复杂度： O(n)
三种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 排序法 | O(n logn) | O(n) | 数据量小，代码简单 |
| 最小堆 | O(n log k) | O(n) | 通用推荐，k 较小时效率高 |
| 桶排序 | O(n) | O(n) | 频次范围有限，追求线性时间 |
关键知识点总结
- 哈希表的应用：快速统计元素频次，O(1)查找和更新
- 优先队列（堆）：Java中
PriorityQueue默认是最小堆，通过自定义比较器可以实现各种排序需求 - 空间换时间：桶排序通过额外的空间实现了线性时间复杂度
- 问题转化思维：将"找最大"转化为 "维护最小堆"，这是 Top K 问题的经典套路
面试技巧
在面试中遇到这类问题时，建议按以下步骤回答：
- 先给出直观解法（排序法），展示基本思路
- 分析时间复杂度瓶颈，提出优化方向
- 介绍堆的优化方案，详细解释为什么用最小堆
- 如果时间允许，提及其他优化方法（如桶排序）
- 讨论各种方法的适用场景
总结
LeetCode 347 题看似简单，但背后蕴含着丰富的数据结构知识和算法思想。掌握这道题的多种解法，不仅能帮你应对类似的Top K 问题，还能加深对哈希表、堆、桶排序等核心数据结构的理解。
记住：在算法的世界里，没有最好的解法，只有最适合的解法。根据具体的数据特征和约束条件选择合适的策略，这才是真正的编程智慧。