题解 | #最小的K个数#

#include <iterator>
#include <unistd.h>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
       int left=0,right=input.size()-1;
       if(input.empty())
            return input;
       quick_select(input,left,right,k);
       return vector<int>(input.begin(),input.begin()+k);
    }
    int partition(vector<int>& input,int left,int right){
        int index=left,val=input[left];
        while(left<right){
            while(left<right && input[right]>=val)
                right--;
            while(left<right  && input[left]<=val)
                left++;
            swap(input[left],input[right]);
        }
        swap(input[left],input[index]);
        return left;
    }
    void quick_select(vector<int>& input,int left,int right,int k){
        int index=partition(input,left,right);
        if(index<k){
            quick_select(input,index+1, right,k);
        }else if(index>k){
            quick_select(input,left, index-1,k);
        }
    }
};

快速选择，应该是时间复杂度最低的方式了吧？