题解 | #最小的K个数#

题目描述
给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
0 <= k <= input.length <= 10000
0 <= input[i] <= 10000

方法一：暴力求解

求解思路
最暴力的求解方式，对给出的数组直接进行排序，然后输出前4个数即可

图片说明

解题代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> myret;
        if (k==0 || k>input.size()) return myret; // 返回结果
        sort(input.begin(), input.end()); // 冒泡排序
        return vector<int>({input.begin(), input.begin()+k}); // 返回结果
    }
};

复杂度分析
时间复杂度：在这里使用的是冒泡排序，平均时间复杂度为 $O( )$
空间复杂度：冒泡排序的空间复杂度， $O(1)$

方法二：优化思路，堆排的思想

求解思路
求解前k个最小的数，我们在暴力解法的基础上，进行改进，使用堆排，让时间复杂度尽可能得低！！！
具体思路：创建一个大根堆，遍历数组的元素，如果堆的大小＜k，则入堆，否则与堆顶元素进行比较，如果堆顶元素大，则出堆，将当前元素入堆即可。

图片说明

解题代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> myres;
        if (k==0 || k > input.size()) return myres;
        priority_queue<int, vector<int>> pp;
        for (const int val : input) 
        {   //遍历数组元素
            if (pp.size() < k) 
            {
                pp.push(val);
            }
            else 
            {
                if (val < pp.top())
                {   //进行比较，如果小，则入堆
                    pp.pop();
                    pp.push(val);
                }

            }
        }
        while (!pp.empty()) // 进行结果的记录
        {
            myres.push_back(pp.top());
            pp.pop();
        }
        return myres; // 返回结果即可！
    }
};

复杂度分析
时间复杂度：堆排序的时间复杂度，为 $O(nlogk)$ ，其中k为大根堆的容量。
空间复杂度：创建大根堆，其容量为k，则空间复杂度为 $O(k)$