最小的K个数

经典问题，3种解法：

1. 先排序，再取前k个数，平均时间复杂度O(nlogn)
2. 使用最小堆，建堆完成后依次交换第一个和第i个元素（i=n,n-1,...,n-k）得到k个最小值，平均时间复杂度O(n+k)
3. 使用快排的patition子程序，逐步逼近第k个数所在的位置，期望平均时间复杂度O(n)，但是前k个数并不是有序状态
   这题并不要求最后的结果有序，所以用第三种方法是最好的，为避免最坏情况，每次patition的基准元素随机选择
   这里不写具体的实现过程，因为是用C++，这里可以直接用STL提供的排序函数
   
   其中：
   1）若需对vector, string, deque, 或array容器进行全排序，你可选择sort或stable_sort；
   2）若只需对vector, string, deque, 或array容器中取得top n的元素，部分排序partial_sort是首选.
   3）若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部 顺序，nth_element是最 理想的；
   4）若你需要从标准序列容器或者array中把满足某个条件 或者不满足某个条件的元素分开，你最好使用partition或stable_partition；
   5）若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。

综上，可以直接用nth_element或者patition_sort即可实现本题：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k == input.size()) {
            return input;
        }
        vector<int> ret;
        if (k > input.size()) {
            return ret;
        }
        nth_element(input.begin(), input.begin() + k, input.end());
        input.resize(k);
        return input;
    }
};