【劍指Offer】29、最小的K個數

題目描述：

  輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4。

  解題思路：

  本題最直覺的解法就是将輸入的n個整數排序，排序之後位于最前面的k個數就是最小的k個數，這取決于排序的時間複雜度，最快為O(nlogn)。

  當我們可以對輸入的數組進行修改時，可以得到一種更快的解法。類似于快速排序的思想，基于Partition函數來解決這個問題，如果我們選取數組的第n個數字（記為key）來進行數組重排，那麼比key小的所有數字都位于數組的左邊，比key大的所有數字都位于key之後，也就是數組的右邊。

  是以，我們隻需要判斷key的下标是否等于k-1，等于時傳回其左邊的K個數便是最小的K個數。當key的下标小于k-1時，就在右邊繼續劃分，反之左邊繼續劃分。由此我們可以得到以下代碼實作，時間複雜度為O(n)。

  程式設計實作（Java）：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //方法一：排序
        //方法二：partition分組
        ArrayList<Integer> res=new ArrayList<>();
        if(input==null || input.length<=0 || k>input.length)
            return res;
        int len=input.length;
        int low=0,high=len-1;
        int index=-1;
        while(low<high && index!=k){
            index=partition(input,low,high);
            if(index>k)
                high=index-1;
            else
                low=index+1;
        }

        for(int i=0;i<k;i++)
            res.add(input[i]);
        return res;
    }
    //劃分算法，傳回的i左邊都比他小，右邊都比他大
    public int partition(int[] array,int low,int high){
        int i=low,j=high;
        int temp=array[low];
        
        while(i<j){
            while(i<j && array[j]>=temp)
                j--;
            if(i<j){
                array[i]=array[j];
                i++;
            }
            while(i<j && array[i]<temp)
                i++;
            if(i<j){
                array[j]=array[i];
                j--;
            }
        }
        array[i]=temp;
        return i;
    }
}