输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

方法1：时间复杂度O(N),会改变原数组

思路：将原数组排序，直接返回前k个最小值即可

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> output;
        if (input.empty()||k>input.size()||k<=0)
            return output;
        sort(input.begin(), input.end());
        for (int i = 0; i < k; i++)
        {
            output.push_back(input[i]);
        }
        return output;
    }
};

方法2：快排思想，时间复杂度O(N),会改变原数组

/*
快排思想：
一次快排确定一个元素位置后，比该元素小的都在其左边，大的都在其右边，
所以我们进行一次或多次快排找到第k个元素（下标为k-1）的正确位置，这样的话，前面就是最小的k个数了，但没有排序是乱序的。
*/
class Solution {
public:
    int quickSort(vector<int>& input, size_t low,size_t high)
    {
        //选取第一个元素作为基数
        int baseVal = input[low];
        size_t i = low, j = high;
        while (i < j)
        {
            //从后往前遍历，一直找到第一个小于baseVal的值
            while (i < j&&input[j] >= baseVal)
                --j;
            //在后边找到小于baseVal的值，交换
            if (i < j)
                input[i++] = input[j];

            while (i < j&&input[i] <= baseVal)
                ++i;
            if (i < j)
                input[j--] = input[i];
        }
        input[i] = baseVal;
        return i;
    }

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

        size_t low = 0, high = input.size() - 1;
        int index = quickSort(input, low,high);
        while (index != k - 1)
        {
            //若baseVal的小标大于k-1，表明k-1在其左边
            if (index > k - 1)
            {
                high = index - 1;
                index = quickSort(input, low, high);
            }
            else
            {
                low = index + 1;
                index = quickSort(input, low, high);
            }
        }
        vector<int> output(input.begin(), input.begin() + k);
        sort(output.begin(), output.end());
        return output;
    }
};

方法3：时间复杂度O(nlogk),不会改变原数组

思路：利用有序容器multiset来完成，它允许存储重复的关键字。
1. 建立有序容器multi,关键字类型为int,先插入vector的前k个数字，且这k个元素在multi中是降序排列的；
2. 当容器满而要插入新元素x时，比较x与multi容器begin()处最大值，若x小于最大值，则先删除最大值，再插入x；否则不做改变，直至遍历完vector。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> &input, int k) {
        //vector<int> output;
        if (input.empty()||k>input.size()||k<=0)
            return {};
        multiset<int> multi;
        multiset<int>::iterator multiIt;
        //向multi插入vector的前k的数,范围为：0---k-1
        multi.insert(input.begin(),input.begin()+k);
        vector<int>::iterator vecIt = input.begin() + k;
        while (vecIt!=input.end())
        {
            //若x小于最大值，则先删除最大值，再插入x
            if (*vecIt < *(--multi.end()))
            {
                multi.erase(--multi.end());
                multi.insert(*vecIt);
            }
            ++vecIt;
        }
        vector<int> output(multi.begin(), multi.end());
        return output;
    }
};