题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
题目链接：https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
第一种方法，用优先级队列构造出最大堆，然后不断更新最大堆，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。但是这里利用集合并不好，手写最大堆会比这个更优，因为在超过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方法来构建出最大最小堆。
代码语言：javascript复制 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代码：
代码语言：javascript复制import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
// [4,5,1,6,2,7,3,8],0
if (input == null || k > input.length || k <= 0) return list;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
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<Integer> it = queue.iterator();
while (it.hasNext()) {
list.add(it.next());
}
return list;
}
} 第二种方法：手写最大堆实现(绝对比PriorityQueue优)
AC代码：
代码语言：javascript复制import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
// [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;
}
}
