剑指 Offer 40. 最小的k个数（堆排序法）

剑指 Offer 40. 最小的k个数（堆排序法）"/>

剑指 Offer 40. 最小的k个数（堆排序法）

用sort的方法就不写了，没有什么意义
下面代码为堆排序的解法
思路都在代码注解中了，用堆挺简单的，还是调用API，没什么要说的
注意要重优先队列的比较方法

public int[] getLeastNumbers(int[] arr, int k) {if (k == 0){return new int[0];}/** 创建一个大根堆，size为k，将数组元素存入堆中，* 如果比堆顶还要到，就直接跳过，* 如果比堆顶小，就将堆底弹出，将该数放出堆中*/PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((v1,v2) -> v2 - v1);for (int i :arr) {if (priorityQueue.size() < k)   priorityQueue.add(i);else if (priorityQueue.peek() > i){priorityQueue.poll();priorityQueue.add(i);}}/** 取出对顶元素*/int[] result = new int[priorityQueue.size()];int i = 0;for (int res:priorityQueue) {result[i++] = res;}return result;