题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
这个题能想到最简单的方法就是利用排序算法对整个数组进行排序，然后取k个值。那么这个算法的复杂度就完全取决与排序算法的复杂度了。
image.png
上面是基于比较的排序算法的时间复杂度
- 但是仔细想一想，对整个数组进行排序这个代价有点大，因为我们根本不需要后面n-k个数据有序。
- 所以应该尝试使用一个数组保存已经扫过的所有的数中最大的k个数，在向后遍历的过程中不断更新这个数组， 这个复杂度大约就是O(n*k)了。
- k数组时用来保存几个有序值的，那么我们可以利用大根堆来替换这个数组，这样这个时间复杂度就可以优化到O（n*logk了）
但是啊。。。这个题目对前面k个数也没有任何顺序要求，所以一定还有更完美的算法等着我们
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if(input == null ||input.length < k || k == 0){
return new ArrayList<Integer>();
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for(int i = 0; i < k; i++){
maxHeap.add(input[i]);
}
for(int i = k; i < input.length; i++){
if(maxHeap.peek() > input[i]){
maxHeap.poll();
maxHeap.add(input[i]);
}
}
return new ArrayList<Integer>(maxHeap);
}
}
