分治/快排思想-最小的k个数

思路

最好写的办法自然是先qsort，然后取第k个元素，但这样把另外n-k个无关的元素也排了序。这题仍然使用升序快排的模板，但是当找到的pivot枢纽元比k大的时候只排它左边的子数组。

另外这题给出的k可能比数组size还大，需要单独处理，代码如下：

class Solution {
public:
    //快排的模板
    void qsortk(int l, int r, vector<int> &a, int k) {
        if(l < r) {
            int i = l, j = r;
            int pivot = a[l];
            while(i < j) {
                while(i < j && a[j] >= pivot) j--;
                if(i < j) a[i] = a[j];
                while(i < j && a[i] <= pivot) i++;
                if(i < j) a[j] = a[i];
            }
            a[i] = pivot;
            if(j < k) {
                qsortk(l, j-1, a, k);
                qsortk(j+1, r, a, k);
            } else {
                qsortk(l, j -1, a, k);
            }
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int size = input.size();
        qsortk(0, size-1, input, k);

        vector<int> res;
        if(k > size) return res;
        res.resize(k);
        for(int i = 0; i < k; i++) {
            res[i] = input[i];
        }
        return res;
    }
};