题目描述
输入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代码：
importjava.util.ArrayList; importjava.util.Comparator; importjava.util.Iterator; importjava.util.PriorityQueue; publicclassSolution { publicArrayList<Integer>GetLeastNumbers_Solution(int [] input, intk) { ArrayList<Integer>list=newArrayList<Integer>(); // [4,5,1,6,2,7,3,8],0if (input==null||k>input.length||k<=0) returnlist; PriorityQueue<Integer>queue=newPriorityQueue<Integer>(newComparator<Integer>(){ publicintcompare(Integeri1, Integeri2) { returni2.compareTo(i1); } }); intlen=input.length; for (inti=0; i<len; ++i) { if (queue.size() !=k) { queue.offer(input[i]); } elseif (queue.peek() >input[i]) { queue.poll(); queue.offer(input[i]); } } Iterator<Integer>it=queue.iterator(); while (it.hasNext()) { list.add(it.next()); } returnlist; } }
第二种方法：手写最大堆实现(绝对比PriorityQueue优)
AC代码：
importjava.util.ArrayList; publicclassSolution { publicArrayList<Integer>GetLeastNumbers_Solution(int[] input, intk) { ArrayList<Integer>list=newArrayList<Integer>(); // [4,5,1,6,2,7,3,8],0if (input==null||k>input.length||k<=0) returnlist; int[] target=newint[k]; intlen=input.length; for (inti=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 (inti=0; i<k; ++i) { list.add(target[i]); } returnlist; } privatevoidheapInsertSiftUp(int[] target, intindex, intx) { while (index>0) { intparent= (index-1) >>>1; if (greater(x, target[parent])) { target[index] =target[parent]; // 往下拉，避免直接上浮覆盖前面的值index=parent; } else { break; } } target[index] =x; } privatebooleangreater(inti, intj) { returni>j; } privatevoidsiftDown(int[] target, intk, intx) { inthalf=target.length>>>1; while (k<half) { intchild= (k<<1) +1; // 默认先左孩子intbig=target[child]; intright=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; } }
==============Talk is cheap, show me the code===============
