专做商品折扣的网站郑州餐饮网站建设公司

专做商品折扣的网站,郑州餐饮网站建设公司,精品课程网站设计与实现,商品网站策划书面试题 17.14 最小 K 个数#xff1a;两种堆解法的“同题不同命” 题目#xff1a;给数组 arr 和整数 k#xff0c;找出最小的 k 个数#xff0c;顺序随意。 数据范围#xff1a;len(arr) 可到 100000#xff0c;k 也可能接近 n。 这题有很多解法#xff08;排序、快…面试题 17.14 最小 K 个数两种堆解法的“同题不同命”题目给数组arr和整数k找出最小的 k 个数顺序随意。数据范围len(arr)可到 100000k也可能接近 n。这题有很多解法排序、快速选择、堆、计数等但面试里最常见、最稳的就是堆。下面的两段代码都用PriorityQueue区别在策略代码1把所有元素扔进小根堆然后弹出 k 次代码2维护一个大小为 k 的大根堆只保留当前最小的 k 个看起来都“用堆”但复杂度完全不是一回事。一、代码1全量小根堆把整个数组堆化代码回顾classSolution{publicint[]smallestK(int[]arr,intk){PriorityQueueIntegerqueuenewPriorityQueue();for(inti0;iarr.length;i){queue.offer(arr[i]);}int[]resnewint[k];for(inti0;ik;i){res[i]queue.poll();}returnres;}}思路拆解PriorityQueueInteger默认是小根堆堆顶是最小值。把 arr 的所有元素逐个offer入堆。因为堆顶永远是最小值所以poll()一次拿到一个当前最小。连续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 个候选代码回顾classIntCmpimplementsComparatorInteger{Overridepublicintcompare(Integero1,Integero2){returno2.compareTo(o1);}}// 新建一个k个元素的大根堆将前K个元素入堆并逐渐从k下标处与已入堆的堆顶元素作比较// 如果k下标元素比已入堆的元素小就将堆顶元素出堆换成k下标元素// 这样一来遍历完整个数组剩下的就是最小的前K个元素classSolution{publicint[]smallestK(int[]arr,intk){PriorityQueueIntegerqueuenewPriorityQueue(newIntCmp());int[]retnewint[k];if(arrnull||k0)returnret;for(inti0;ik;i){queue.offer(arr[i]);}for(intik;iarr.length;i){intpeekqueue.peek();if(arr[i]peek){queue.poll();queue.offer(arr[i]);}}for(inti0;ik;i){ret[i]queue.poll();}returnret;}}思路拆解这段是“面试最推荐”的堆解法关键技巧用大根堆维护“当前最小 k 个数”。大根堆堆顶是“当前这 k 个数里最大的那个”一旦遇到更小的数就把堆顶最大的踢出去用新来的小数顶替这样遍历完数组堆里剩下的就是最小 k 个。具体流程自定义比较器IntCmp把 PriorityQueue 变成大根堆compare(o1, o2) o2.compareTo(o1)⇒ 反序 ⇒ 大根堆先把前 k 个元素入堆此时堆里有 k 个候选。从第 k 个位置开始遍历剩余元素取堆顶peek当前候选集合中最大的那个如果arr[i] peek说明新来的数比候选集合里“最差的那个”还好把堆顶弹出再把新数放进去否则忽略因为它不可能进入最小 k 集合最后把堆里 k 个数弹出来就是答案顺序随意符合题意。正确性直觉为什么一定对可以把堆里元素理解成“我目前见过的最小 k 个”。堆顶保存的是这 k 个里最大的那个也就是“门槛”新数如果不比门槛小那它进来只会把集合变差所以直接丢弃新数如果比门槛小就说明它应该进入最小 k 集合于是替换掉“门槛那个人”遍历完所有元素后所有“有资格进入最小 k”集合的元素都已经尝试过替换堆里自然就是全局最小 k 个。复杂度初始化入堆 k 次O(k log k)遍历剩余 n-k 个元素每次最多一次polloffer每次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时间复杂度代码1O(n log n k log n)≈O(n log n)代码2O(n log k)当k n比如 n100000, k100log k和log n的差距会直接体现在运行时间上。2空间复杂度代码1O(n)堆存了全部元素代码2O(k)只存候选的 k 个当 n 很大时空间差距也很明显。3常数开销与工程细节两段代码都使用PriorityQueueInteger会有**装箱/拆箱int ↔ Integer**开销。代码2自定义比较器会多一次比较器回调但相比减少大量堆规模这点成本通常是值得的。如果追求极致性能尤其面试里可以顺嘴提一句可以考虑用原生数组实现二叉堆避免装箱或者用快速选择QuickSelect平均 O(n) 时间、O(1) 额外空间但实现更容易写错4适用场景k 接近 n两者差距缩小代码1也能接受写起来快。k 很小代码2明显更优是“标准工程解”。5边界情况鲁棒性代码1如果k arr.length会在poll()时出现问题题目保证k len(arr)所以没事但现实代码最好加保护。代码2已处理k0但如果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已经是非常漂亮、非常稳的答案了。