【Java】TOP-K问题

题目

https://leetcode.cn/problems/smallest-k-lcci/description/

算法的思路详解

整体排序法

核心思路：
既然要找最小的前 K 个元素，那就干脆把所有元素排好序，然后直接取前 K 个。

执行步骤：

1. 将整个数组从小到大排序
2. 取出排序后数组的前 K 个元素

优点：代码最简单，思路最直接
缺点：做了很多"无用功"——我们只需要前 K 小，却把整个数组都排好了

整体建立小顶堆法

核心思路：
用小顶堆的特性——堆顶永远是最小值。把所有元素放入堆中，然后依次弹出堆顶，弹出来的就是从小到大的顺序。

执行步骤：

1. 把所有 N 个元素放入一个小顶堆（建堆 O(N)）
2. 从堆顶弹出元素，弹出来的就是当前最小值
3. 重复弹出 K 次，得到前 K 小的元素

优点：比排序法稍快（建堆 O(N) vs 排序 O(N log N)）
缺点：仍然需要存储全部 N 个元素

大小为 K 的大顶堆法

核心思路：
维护一个"门槛"——只关心前 K 小的元素，大于门槛的统统不要。用大顶堆来记录当前找到的 K 个候选，堆顶是这 K 个里面最大的（也就是当前的"门槛"）。

执行步骤：

1. 先用前 K 个元素建一个大顶堆（堆顶是这 K 个中最大的）
2. 遍历剩下的 N-K 个元素：
   • 如果当前元素小于堆顶（门槛），说明它应该进入前 K 小
   • 把堆顶（最大的那个）踢出去，把当前元素加进来
3. 遍历结束后，堆里剩下的就是前 K 小的元素

为什么用大顶堆？
因为我们要快速知道当前 K 个候选中的最大值是谁，新来的只要比它小，就能替换掉它。

优点：内存占用极小（只存 K 个元素），适合海量数据（比如 10 亿个数找前 100 小）
缺点：实现稍复杂

code

整体排序法

// 1. 整体排序法publicstaticList<Integer>topKBySorting(int[]arr,intk){if(arr==null||arr.length==0||k<=0)returnnewArrayList<>();int[]copy=Arrays.copyOf(arr,arr.length);Arrays.sort(copy);List<Integer>result=newArrayList<>();for(inti=0;i<k&&i<copy.length;i++){result.add(copy[i]);}returnresult;}

整体建立小顶堆法

// 2. 整体建立小顶堆法（把所有元素放入小顶堆，再弹出前K个）publicint[]smallestK(int[]arr,intk){int[]result=newint[k];if(arr==null||arr.length==0||k<=0)returnresult;PriorityQueue<Integer>heap=newPriorityQueue<>();// 小顶堆for(intnum:arr){heap.offer(num);}for(inti=0;i<k;i++){result[i]=(heap.poll());}returnresult;}

大小为K的大顶堆法

// 3. 大小为K的大顶堆法（推荐，适合大数据量）classIntCmpimplementsComparator<Integer>{@Overridepublicintcompare(Integero1,Integero2){returno2.compareTo(o1);}}classSolution{publicint[]smallestK(int[]arr,intk){int[]result=newint[k];if(arr==null||arr.length==0||k<=0)returnresult;PriorityQueue<Integer>heap=newPriorityQueue<>(newIntCmp());// 大顶堆for(inti=0;i<k;i++){heap.offer(arr[i]);}for(intj=k;j<arr.length;j++){if(heap.peek()>arr[j]){heap.poll();heap.offer(arr[j]);}}for(intl=0;l<k;l++){result[l]=(heap.poll());}returnresult;}}

三种方法对比