NC119：最小的K个数

解法1：优先级队列

优先级队列：小根堆

    PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer a,Integer b){
            return a.compareTo(b);
        }
    });
//  PriorityQueue<Integer> queue = new PriorityQueue();

最小k个数：大根堆

PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>
                                       (k,new Comparator<Integer>(){
        @Override
        public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);
            }
        });
PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(k,(a,b)->b.compareTo(a));     

思路：最大优先队列，无论入队顺序，当前最大的元素优先出队。
用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。堆节点的上浮和下沉的时间复杂度为logN，所以优先队列入队和出队的时间复杂度也为logN

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        if(k <=0 || k > input.length || input.length==0){
            return new ArrayList<Integer>(0);
        }
        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);
    }
}

解法2：冒泡排序的改进：冒K次

冒泡排序的思想，只不过最外层循环K次就可以了；
也就是说不用全部排序；只挑出符合提议的K个就可以；

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        if (k > input.length) {
            return al;
        }
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < input.length - i - 1; j++) {
                if (input[j] < input[j + 1]) {
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                }
            }
            al.add(input[input.length - i - 1]);
        }
        return al;
    }

解法3：堆排序 / 快速排序

//快速排序
import java.util.*;
public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        quicksort(a,0,n-1);
        return a[n-K];
    }
    public void quicksort(int[] a,int start,int end){
        if(start<end){
            int part=partition(a,start,end);
            quicksort(a,start,part-1);
            quicksort(a,part+1,end);
        }
    }
    public int partition(int[]a,int l,int r){
        int pivot=l;
        int index=l+1;
        for(int i=l+1;i<=r;i++){
            if(a[i]<a[pivot]){
                swap(a,i,index);
                index++;
            }
        }
        swap(a,pivot,index-1);
        return index-1;
    }
    public void swap(int[] a,int i,int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
}

//堆排序
public findKth(int[] a, int n, int K) {
    heapSort(a);
    return a[n-K];
}

public static void heapSort(int[] arr){
    if(arr == null || arr.length<2){
        return;
    }
    for(int i=0;i<arr.length;i++){
        heapInsert(arr,i); //构造完全二叉树
    }
    int size = arr.length;
    swap(arr,0,--size);
    while(size>0){
        heapify(arr,0,size);// 最后一个数与根交换
        swap(arr,0,--size);
    }

}
//判断该结点与父结点的大小，大结点一直往，建立大根堆
public static void heapInsert(int[] arr,int index){
    while(arr[index]>arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index=(index-1)/2;
    }
}

//一个值变小往下沉的过程
public static void heapify(int[] arr,int index,int size){
    int left=index*2+1;
    while(left<size){
        int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left;
        largest = arr[largest] > arr[index] ? largest :index;
        if(largest==index){
            break;
        }
        swap(arr,largest,index);
        index=largest;
        left=index*2 +1;

    }
}

//交换函数
public static void swap(int[] arr, int i, int j){
    int tmp;
    tmp=arr[i];
    arr[i]=arr[j];
    arr[j]=tmp;
}