盐城市网站建设_网站建设公司_Bootstrap_seo优化

面试题 17.14 最小 K 个数：两种堆解法的“同题不同命”

题目：给数组arr和整数k，找出最小的 k 个数，顺序随意。

数据范围：len(arr)可到 100000，k也可能接近 n。

这题有很多解法（排序、快速选择、堆、计数等），但面试里最常见、最稳的就是堆。下面的两段代码都用PriorityQueue，区别在策略：

• 代码1：把所有元素扔进小根堆，然后弹出 k 次
• 代码2：维护一个大小为 k 的大根堆，只保留当前最小的 k 个

看起来都“用堆”，但复杂度完全不是一回事。

一、代码1：全量小根堆（把整个数组堆化）

代码回顾

classSolution{publicint[]smallestK(int[]arr,intk){PriorityQueue<Integer>queue=newPriorityQueue<>();for(inti=0;i<arr.length;i++){queue.offer(arr[i]);}int[]res=newint[k];for(inti=0;i<k;i++){res[i]=queue.poll();}returnres;}}

思路拆解

1. PriorityQueue<Integer>默认是小根堆（堆顶是最小值）。
2. 把 arr 的所有元素逐个offer入堆。
3. 因为堆顶永远是最小值，所以poll()一次拿到一个当前最小。
4. 连续poll()k 次，就拿到了最小的 k 个数。

正确性为什么成立？

因为小根堆的定义保证：每次poll()返回的是当前集合里的最小值。把 n 个数都放进去后，连续弹 k 次，必然得到全局最小的 k 个。

复杂度

• 建堆：n 次offer，每次O(log n)⇒O(n log n)

  • 细节：Java 的 PriorityQueue 没有直接暴露“heapify(数组)”构造（其实可以通过new PriorityQueue<>(Collection)走近似 heapify），你这里是逐个入堆，所以是n log n。

• 弹出 k 次：k * O(log n)⇒O(k log n)

• 总时间：O(n log n + k log n)，通常写作O((n + k) log n)

• 空间：堆里存 n 个元素 ⇒O(n)

这段代码的优缺点

优点：

• 写起来最简单，几乎不容易错
• 当 k 接近 n 时，复杂度和代码2差距不大（反正都要“接近全取”）

缺点：

• 堆存了全部 n 个元素，空间 O(n)
• 当 k 很小而 n 很大时，非常浪费：明明只要 k 个最小，却维护了 n 个

二、代码2：维护 k 大小的大根堆（只保留最小 k 个候选）

代码回顾

classIntCmpimplementsComparator<Integer>{@Overridepublicintcompare(Integero1,Integero2){returno2.compareTo(o1);}}// 新建一个k个元素的大根堆，将前K个元素入堆，并逐渐从k下标处与已入堆的堆顶元素作比较// 如果k下标元素比已入堆的元素小，就将堆顶元素出堆，换成k下标元素// 这样一来，遍历完整个数组，剩下的就是最小的前K个元素classSolution{publicint[]smallestK(int[]arr,intk){PriorityQueue<Integer>queue=newPriorityQueue<>(newIntCmp());int[]ret=newint[k];if(arr==null||k==0)returnret;for(inti=0;i<k;i++){queue.offer(arr[i]);}for(inti=k;i<arr.length;i++){intpeek=queue.peek();if(arr[i]<peek){queue.poll();queue.offer(arr[i]);}}for(inti=0;i<k;i++){ret[i]=queue.poll();}returnret;}}

思路拆解（这段是“面试最推荐”的堆解法）

关键技巧：用大根堆维护“当前最小 k 个数”。

• 大根堆堆顶是“当前这 k 个数里最大的那个”
• 一旦遇到更小的数，就把堆顶（最大的）踢出去，用新来的小数顶替

这样遍历完数组，堆里剩下的就是最小 k 个。

具体流程：

1. 自定义比较器IntCmp，把 PriorityQueue 变成大根堆：

   • compare(o1, o2) = o2.compareTo(o1)⇒ 反序 ⇒ 大根堆

2. 先把前 k 个元素入堆：此时堆里有 k 个候选。

3. 从第 k 个位置开始遍历剩余元素：

   • 取堆顶peek（当前候选集合中最大的那个）

   • 如果arr[i] < peek：

     • 说明新来的数比候选集合里“最差的那个”还好
     • 把堆顶弹出，再把新数放进去

   • 否则忽略（因为它不可能进入最小 k 集合）

4. 最后把堆里 k 个数弹出来就是答案（顺序随意，符合题意）。

正确性直觉（为什么一定对）

可以把堆里元素理解成“我目前见过的最小 k 个”。

• 堆顶保存的是这 k 个里最大的那个，也就是“门槛”
• 新数如果不比门槛小，那它进来只会把集合变差，所以直接丢弃
• 新数如果比门槛小，就说明它应该进入最小 k 集合，于是替换掉“门槛那个人”

遍历完所有元素后，所有“有资格进入最小 k”集合的元素都已经尝试过替换，堆里自然就是全局最小 k 个。

复杂度

• 初始化入堆 k 次：O(k log k)

• 遍历剩余 n-k 个元素：

  • 每次最多一次poll+offer，每次O(log k)⇒ 最坏O((n-k) log k)

• 总时间：O(k log k + (n-k) log k)≈O(n log k)

• 空间：堆里只存 k 个元素 ⇒O(k)

当 k 远小于 n 时，log k比log n小很多，而且空间也从 O(n) 降到 O(k)，差距非常实在。

三、两段代码的“多维对比”（面试官最爱问的部分）

1）时间复杂度

• 代码1：O(n log n + k log n)≈O(n log n)
• 代码2：O(n log k)

当k << n（比如 n=100000, k=100），log k和log n的差距会直接体现在运行时间上。

2）空间复杂度

• 代码1：O(n)（堆存了全部元素）
• 代码2：O(k)（只存候选的 k 个）

当 n 很大时，空间差距也很明显。

3）常数开销与工程细节

• 两段代码都使用PriorityQueue<Integer>，会有**装箱/拆箱（int ↔ Integer）**开销。
• 代码2自定义比较器会多一次比较器回调，但相比减少大量堆规模，这点成本通常是值得的。

如果追求极致性能（尤其面试里可以顺嘴提一句），可以考虑：

• 用原生数组实现二叉堆（避免装箱）
• 或者用快速选择（QuickSelect）平均 O(n) 时间、O(1) 额外空间（但实现更容易写错）

4）适用场景

• k 接近 n：两者差距缩小，代码1也能接受，写起来快。
• k 很小：代码2明显更优，是“标准工程解”。

5）边界情况鲁棒性

• 代码1：如果k > arr.length会在poll()时出现问题（题目保证k <= len(arr)，所以没事，但现实代码最好加保护）。
• 代码2：已处理k==0，但如果arr.length < k（同样题目保证不会发生），初始化入堆会越界；工程上也可以加个k = Math.min(k, arr.length)。

四、一个小建议：代码1可以更快一点（可选优化点）

代码1逐个offer是O(n log n)；如果把数组先放进集合再构造 PriorityQueue，有机会让底层做一次更接近 heapify 的构建（接近O(n)），但 Java 的实现细节不总是等价于传统 heapify。面试时可以提优化方向，但通常不必执着。

五、总结：到底该选哪段？

一句话推荐：

• 想写得简单：代码1（全量小根堆）
• 想写得高效（尤其 k 远小于 n）：代码2（大小为 k 的大根堆，经典最优解之一）

从面试角度，代码2更像“理解题意后的最佳实践”，也最能体现对复杂度的把控能力：
用“大根堆当门槛”这个思路，把问题从log n压到了log k，而且空间从n压到了k——这是实打实的算法优化。

如果还想再进阶一步，那就是 QuickSelect（快速选择）路线：平均 O(n)、最坏 O(n²)，需要随机化或三数取中来稳住。但在多数面试场景里，代码2已经是非常漂亮、非常稳的答案了。