快速选择，时间复杂度O(n)，空间O(n)

用快排的变体，快速选择算法，选择一个pivot，对数组进行划分，pivot左边小于vt[pivot], 右边则大于。 然后利用二分快速确定partion区间，直到收敛到k-1. 算法复杂度O(n)，n为数组长度。 rand()

class Solution {
public:
    int partion(vector<int>& vt, int s, int e) {
        if (s >= e) return s;
        //随机选择一个哨兵，以便算法时间复杂度平均期望为O(n)
        int pivot = rand() % (e - s) + s;
        swap(vt[pivot], vt[e]);
        int i = s - 1, j = s;
        while (j < e) {
            if (vt[j] < vt[e]) swap(vt[++i], vt[j]);
            ++j;
        }
        swap(vt[++i], vt[e]);
        return i;
    }

    int recursive(vector<int>& vt, int s, int e, int k) {
        int mid = partion(vt, s, e);
        if (mid == k-1) {
            return mid;
        }
        else if (mid < k-1) return recursive(vt, mid + 1, e, k);
        else return recursive(vt, s, mid - 1, k);
    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (input.empty() || k > input.size() || k <= 0) return ret;

        int idx = recursive(input, 0, input.size() - 1, k);       
        for (int i = 0; i <= idx; ++i) ret.push_back(input[i]);
        return ret;
    }
};