题解 | #最小的K个数#

快速选择(Quickselect)算法，C++ STL的nth_element正是这个。

平均时间复杂度O(n)，空间复杂度O(1)。

public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>::iterator target_pos = input.begin() + k - 1;
        nth_element(input.begin(), target_pos, input.end());
        return vector<int>(input.begin(), input.begin() + k);
    }
};