剑指offer----最小的k个数

题目：输入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);
    }

}