【Java】TOP-K问题

TOP-K问题题目算法的思路详解整体排序法整体建立小顶堆法大小为 K 的大顶堆法code整体排序法整体建立小顶堆法大小为K的大顶堆法三种方法对比题目https://leetcode.cn/problems/smallest-k-lcci/description/算法的思路详解整体排序法核心思路既然要找最小的前 K 个元素那就干脆把所有元素排好序然后直接取前 K 个。执行步骤将整个数组从小到大排序取出排序后数组的前 K 个元素优点代码最简单思路最直接缺点做了很多无用功——我们只需要前 K 小却把整个数组都排好了整体建立小顶堆法核心思路用小顶堆的特性——堆顶永远是最小值。把所有元素放入堆中然后依次弹出堆顶弹出来的就是从小到大的顺序。执行步骤把所有 N 个元素放入一个小顶堆建堆 O(N)从堆顶弹出元素弹出来的就是当前最小值重复弹出 K 次得到前 K 小的元素优点比排序法稍快建堆 O(N) vs 排序 O(N log N)缺点仍然需要存储全部 N 个元素大小为 K 的大顶堆法核心思路维护一个门槛——只关心前 K 小的元素大于门槛的统统不要。用大顶堆来记录当前找到的 K 个候选堆顶是这 K 个里面最大的也就是当前的门槛。执行步骤先用前 K 个元素建一个大顶堆堆顶是这 K 个中最大的遍历剩下的 N-K 个元素如果当前元素小于堆顶门槛说明它应该进入前 K 小把堆顶最大的那个踢出去把当前元素加进来遍历结束后堆里剩下的就是前 K 小的元素为什么用大顶堆因为我们要快速知道当前 K 个候选中的最大值是谁新来的只要比它小就能替换掉它。优点内存占用极小只存 K 个元素适合海量数据比如 10 亿个数找前 100 小缺点实现稍复杂code整体排序法// 1. 整体排序法publicstaticListIntegertopKBySorting(int[]arr,intk){if(arrnull||arr.length0||k0)returnnewArrayList();int[]copyArrays.copyOf(arr,arr.length);Arrays.sort(copy);ListIntegerresultnewArrayList();for(inti0;ikicopy.length;i){result.add(copy[i]);}returnresult;}整体建立小顶堆法// 2. 整体建立小顶堆法把所有元素放入小顶堆再弹出前K个publicint[]smallestK(int[]arr,intk){int[]resultnewint[k];if(arrnull||arr.length0||k0)returnresult;PriorityQueueIntegerheapnewPriorityQueue();// 小顶堆for(intnum:arr){heap.offer(num);}for(inti0;ik;i){result[i](heap.poll());}returnresult;}大小为K的大顶堆法// 3. 大小为K的大顶堆法推荐适合大数据量classIntCmpimplementsComparatorInteger{Overridepublicintcompare(Integero1,Integero2){returno2.compareTo(o1);}}classSolution{publicint[]smallestK(int[]arr,intk){int[]resultnewint[k];if(arrnull||arr.length0||k0)returnresult;PriorityQueueIntegerheapnewPriorityQueue(newIntCmp());// 大顶堆for(inti0;ik;i){heap.offer(arr[i]);}for(intjk;jarr.length;j){if(heap.peek()arr[j]){heap.poll();heap.offer(arr[j]);}}for(intl0;lk;l){result[l](heap.poll());}returnresult;}}三种方法对比方法思路整体排序全部排好序再取前 K 个整体小顶堆所有元素进堆再弹出 K 次大小为 K 的大顶堆维持一个 K 大小的候选池池里最大的就是门槛方法时间复杂度空间复杂度说明整体排序O(N log N)O(N) 或 O(log N)原地排序简单直接但不需要全部排序整体小顶堆O(N K log N)O(N)建立堆 O(N)弹出 K 次 O(K log N)大小为 K 的大顶堆O(N log K)O(K)最适合流式/海量数据内存占用最小