题解 | #最小的K个数#

//快排
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        if(k==0)return ans;
        int  le=0,r=input.size()-1;
        quick_sort(input,le,r);
        for(int i=0;i<k;i++)
        {
            ans.push_back(input[i]);
        }
        return ans;
    }
    void quick_sort(vector<int>& input,int le,int r)
    {
        if(le==r)return ;//因为while循环处找的i和j不会越过边界，用等于就行
        int  mid  = le+(r-le)/2;
        //用中间的数而是开头只是想中间的时间复杂度可能低点
        int k = input[mid];
        int i=le-1,j=r+1;//为了防止第一个元素和最后一个元素不参加比较
        while(i<j)
        {
          //之所以使用i++和j--是因为一旦出现重复元素会出现死循环
          //为了使交换完元素后两指针移动
            do i++;
          //使用<而不是<=是为了防止i直接越界，如【0，1，2，1，2】;
          	   while(input[i]<k);//
            do j--;//下同理
               while(input[j]>k);
            if(i<j)swap(input[i],input[j]);
        }
       //此处的i和j有两种情况:
       //1.i==j:那么左边界[le,i],右[i+1,r]或左[le,j],右[j+1,r]; 如:（1，2，3）
       //2.i>j:那么需要左边界[le,j],右[j+1,r] 或者左[le,i-1],右[i,r]; 如(6,6)  
       //综上使用左[le,j],右[j+1,r]
        quick_sort(input,le,j);//其实当i==j的时候，i和j都类似mid向下取整
        quick_sort(input,j+1,r);
    }
};