題目描述
輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,。

思路
快速排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len==0 || k>len ||k<=0) 
            return vector<int>();
        if(len==k)
            return input;
        
        int start=0,end=len-1;
        int index=partition(input,start,end);
        while(index!=(k-1)){
            if(index>k-1){
                end=index-1;
                index=partition(input,start,end);
            }else{
                start=index+1;
                index=partition(input,start,end);
            }
        }
        vector<int> res(input.begin(),input.begin()+k);
        return res;
    }
    
    int partition(vector<int> &nums, int begin, int end){
        int low=begin, high=end;
        int pivot=nums[begin];
        while(low<high){
            while(low<high && nums[high]>=pivot)
                high--;
            if(low<high)
                nums[low++]=nums[high];
            while(low<high && nums[low]<=pivot)
                low++;
            if(low<high)
                nums[high--]=nums[low];
        }
        nums[low]=pivot;
        return low;
    }
};