题解 | #最小的K个数#

题目：最小的K个数

描述：给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

示例1：输入：[4,5,1,6,2,7,3,8],4，返回值：[1,2,3,4]

解法一：

解题思路：乍一看，这种题目相对来说比较简单，在思考的时候，可以想一种比较简单的算法，因为想要找到数组中最小的k个数，可以直接调用C++里边的sort()函数，将数组中的元素，按照从小到大的顺序进行排序，排序好以后，新建一个容器对象：res，整一个for循环，将排序好的原数组里边的数字按0-k直接输出，将所有输出的数字push_back到res容器里边，然后直接将res输出即可。

在笔者进行程序验证的时候，疏忽了一点，就是关于K >数组的长度，那么返回一个空的数组，这种直接添加一个if语句判断即可完成相应操作。

实例分析：[4,5,1,6,2,7,3,8],4

在这个数组中，要寻找最小的4个数的值，首先建立一个新的容器对象res，方便以后进行判断。

具体C++代码如下所示：

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

其时间复杂度为O(n*logn)。

解法二：

思路分析：因为本题只需要前k个数，所以也可以采用部分选择排序法进行排序，只需要通过K次排序找到K个最小的数即可。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int sz = input.size();
        vector<int> vec;
        if (sz == 0 || k <= 0 || sz < k)
            return vec;
        for (int i = 0; i < k; ++i)
        {
            for (int j = i + 1; j < sz; ++j)
            {
                if (input[i] > input[j])
                    swap(input[i], input[j]);
            }
            vec.push_back(input[i]);
        }
        return vec;
    }
};