剑指offer：最小k个数

1. 题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

2. 方法：

(1)基于堆排序算法，构建最大堆。时间复杂度为O(nlogk)

(2)如果用快速排序，时间复杂度为O(nlogn)；

(3)如果用插入排序，时间复杂度为O(n^2)。

3.算法

(1):最大堆

/*
1.判断特殊情况：k的大小，k==0或k的长度大于input返回空。
2.设置PriorityQueue<Integer>的比较为降序（最大堆），默认的自然序为升序。（用PriorityQueue实现堆，非线程安全）
3.在堆中添加元素,若堆大小<k，直接添加；否则，将最大堆的堆顶与input[i]比较，小于堆顶则poll堆顶，设为null，并将input[i]添加进堆顶。
4. poll堆，添加进arraylist。因为是大顶堆，所以在第一位添加：list(0,queue.poll()).
*/
public  static ArrayList<Integer> function3(int [] input,int k){
        ArrayList<Integer> list = new ArrayList<>();
        if (k > input.length|k==0) {
            return list;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
//            降序o2>o1，o2在前
//            自然序为升序
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i=0;i<input.length;++i){
            if(queue.size()<k){
                queue.offer(input[i]);
            }else {
                if (queue.peek()>input[i]){
                    Integer temp=queue.poll();
                    temp=null;
                    queue.offer(input[i]);
                }
            }
        }
        while (!queue.isEmpty()){
            list.add(0,queue.poll());
        }
        return list;
    }

用PriorityQueue实现最大堆，PriorityQueue有动态维护最大堆的功能。详情： 

(2):快排

public static ArrayList<Integer> function1(int [] array,int k){
        ArrayList<Integer> list=new ArrayList<>();

        Arrays.sort(array);
        for (int i = 0; i < k; i++) {
            list.add(array[i]);
        }
        return list;
    }

使用Arrays.sort()函数，自动排序。 

(3):插入

/**
直接在list.add时排序
1. 若list长度<k 或者 input[i]<list,get(k-1)，则在list中找到合适位置插入，最后截取list的前k个元素返回。
2. 插入：若list长度>=k,则在前k个元素中比较；否则（list长度小于k）在list所有元素中比较。
3.查找插入位置：遍历list，从k-1到list.get(t)>input[i],则在t之后插入（因为list.get(t)<input）
tips：1. 循环条件不要少了t>=0,若list.get(t-1)会报错。
！！！2. arraylist.subList(start,end)，截取长度为（end-start）的List，注意返回为List不是ArrayList，且为视图（对它改变会改变原对象）.
3. List->ArrayList：新建arraylist对象，再使用addall()函数。


*/
public static ArrayList<Integer> function2(int [] input,int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (k > input.length|k==0) {
            return list;
        }
        list.add(input[0]);
        for (int i = 1; i < input.length; i++) {
              if (i < k||input[i] < list.get(k - 1)) {
//                在合适位置插入
                int t=list.size()>=k?k-1:list.size()-1;
                for (; t>=0&&list.get(t) > input[i]; t--) ;
                list.add(t + 1, input[i]);
            }
        }
        ArrayList<Integer> newlist=new ArrayList<>();
        newlist.addAll(list.subList(0,k));
        return  newlist;
    }