题解 | #最小的K个数#

1.思路，快排，partition思路。 2.vector必须传引用才能复制，使用swap方法。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<=k) {
            return input;
        }
        int start = 0, end = input.size()-1;
        while(true) {
            int p = partition(input,start,end);
            if (p==k) {
                return vector<int>(input.begin(),input.begin()+p);
            }
            if(p>k) {
                end = p-1;
            } else {
                start = p+1;
            }
            for (const auto& i : input)
                std::cout << i << ' ';
            cout<<endl;
        }
    }
    
    int partition(vector<int>&input,int start,int end) {
        if (start==end) {
            return start;
        }
        int i=start-1,x=input[end];
        for (int j=start;j<end;j++) {
            if (input[j]<x) {
                i++;
                swap(input[i],input[j]);
            }
        }
        swap(input[i+1],input[end]);
        return i+1;
    }
};