本文共 3976 字，大约阅读时间需要 13 分钟。
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
题目链接：
第一种方法，用优先级队列构造出最大堆，然后不断更新最大堆，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。但是这里利用集合并不好，手写最大堆会比这个更优，因为在超过k个数的时候，优先级队列需要poll和offer(或者add)操作，poll会下沉恢复堆有序（源码思路：将数组最后一个元素赋给堆顶，size-1，然后从堆顶往下一个个比较，相当于把堆顶往下沉，然后到合适位置，堆顶下沉只会赋值一次，并不是下沉的时候比较交换），offer会上升恢复堆有序（源码思路：从堆底往上一个个比较，相当于把堆底往上浮，堆底上浮只会赋值一次到合适位置，并不是上浮的时候比较交换），而如果手写堆实现的话，仅仅只需要将堆顶元素替换再下沉，就没有了上升恢复堆有序的环节。如果是100W个数找最小的5个数，假如情况比较糟糕，每次都需要更新最大堆堆顶，如果那么使用PriorityQueue将要多做999995（99W近100W）次上升恢复堆有序的操作。可以看一下PriorityQueue的源码就知道。
并且最后迭代的时候要么foreach要么iterator，本质就是iterator迭代。为什么不用for循环去list.add(queue.poll())？虽然也可以出结果，但是queue的poll方法会有下沉恢复堆有序操作，而iterator不会，仅仅是遍历数组。最后返回的ArrayList是满足要求的数字但不一定有序(因为数组堆不一定有序)，返回这个ArrayList，最后判题系统应该会排序后来判断结果对不对。
PS：优先级队列的传入比较器参数new Comparator是需要在上浮和下沉的时候将回调我们重写的compare方法来构建出最大最小堆。
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
public int compare(Integer i1, Integer i2) { return i2.compareTo(i1); } });这里如果i1.compareTo(i2)那么就是构建的小顶堆（其实默认也是小顶堆），如果i2.compareTo(i1)就是大顶堆。
AC代码：
import java.util.ArrayList;import java.util.Comparator;import java.util.Iterator;import java.util.PriorityQueue;public class Solution { public ArrayList GetLeastNumbers_Solution(int [] input, int k) { ArrayList list = new ArrayList (); // [4,5,1,6,2,7,3,8],0 if (input == null || k > input.length || k <= 0) return list; PriorityQueue queue = new PriorityQueue (new Comparator (){ public int compare(Integer i1, Integer i2) { return i2.compareTo(i1); } }); int len = input.length; for (int i = 0; i < len; ++i) { if (queue.size() != k) { queue.offer(input[i]); } else if (queue.peek() > input[i]) { queue.poll(); queue.offer(input[i]); } } Iterator it = queue.iterator(); while (it.hasNext()) { list.add(it.next()); } return list; }}
第二种方法：手写最大堆实现(绝对比PriorityQueue优)
AC代码：
import java.util.ArrayList;public class Solution { public ArrayList GetLeastNumbers_Solution(int[] input, int k) { ArrayList list = new ArrayList (); // [4,5,1,6,2,7,3,8],0 if (input == null || k > input.length || k <= 0) return list; int[] target = new int[k]; int len = input.length; for (int i = 0; i < len; ++i) { if (i < k) { target[i] = input[i]; heapInsertSiftUp(target, i, target[i]); } else { if (target[0] > input[i]) { // 最大堆下沉 target[0] = input[i]; siftDown(target, 0, target[0]); // 相比优先级队列，这里不会offer操作(里面有上浮)，少了一步上浮调整，效率高了不止一丁点 } } } for (int i = 0; i < k; ++i) { list.add(target[i]); } return list; } private void heapInsertSiftUp(int[] target, int index, int x) { while (index > 0) { int parent = (index - 1) >>> 1; if (greater(x, target[parent])) { target[index] = target[parent]; // 往下拉，避免直接上浮覆盖前面的值 index = parent; } else { break; } } target[index] = x; } private boolean greater(int i, int j) { return i > j; } private void siftDown(int[] target, int k, int x) { int half = target.length >>> 1; while (k < half) { int child = (k << 1) + 1; // 默认先左孩子 int big = target[child]; int right = child + 1; if (right < target.length && greater(target[right], big)) { big = target[right]; child = right; // 可以直接一步big = target[child = right]; } if (greater(x, big)) // x比子节点中的最大值还大，已经是大顶堆了 break; // 往上拉不动了，准备退出把最初堆顶的结点赋值到上一个结点 target[k] = big; // 往上拉 k = child; } target[k] = x; }}
相关文章另一篇topK问题：
==============Talk is cheap, show me the code===============
转载地址：https://liuchenyang0515.blog.csdn.net/article/details/85398427 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
