题解 | #最小的K个数 快拍排思想#

对数组[l, r]一次快排partition过程可得到，[l, p), p, [p+1, r)三个区间,[l,p)为小于等于p的值
[p+1,r)为大于等于p的值。
然后再判断p，利用二分法

如果[l,p), p，也就是p+1个元素（因为下标从0开始），如果p+1 == k, 找到答案
2。 如果p+1 < k, 说明答案在[p+1, r)区间内，
3， 如果p+1 > k , 说明答案在[l, p)内
代码

class Solution {
public:

int partition(vector<int> &input, int l,int r)
{
    int left=l,right=r;
    int first=input[left];//取出第一个元素作为标志元素
    while(left<right){
        while(left<right && input[right]>=first) right--;
        swap(input[left],input[right]);//右边小于标志元素的元素换到左边
        while(left<right && input[left]<first) left++;
        swap(input[left],input[right]);//左边大于标志元素的元素换到右边
    }
        //得到left左边的元素都比input[left]小,left右边的元素都比input[left]大(不一定有序)
    return left;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    vector<int> ret;
    int left=0,right=input.size()-1;
    if(k==0 || k>input.size()) return ret;
    while(left<=right){
        int p=partition(input,left,right);//得到标志元素索引
        if(p+1 == k){//如果索引前边元素(包含)个数等于k,直接返回
            return vector<int>(input.begin(),input.begin()+k);
        }
         if(p+1 < k){//如果索引前边元素(包含)个数小于k,第k小的元素肯定在标志元素右边
            left=p+1;
        }else //第k小的元素肯定在标志元素左边
        {
            right=p;    
        }
        //cout<<p<<endl;
        }
        return ret;

    }
};