题解 | #最小的K个数#

##思路： 题目的主要信息：

• 对于一个给定无序数组，返回最小的k个元素，顺序由小到大
• k和数组有特殊情况需要单独讨论

方法一：sort排序法

具体做法：

这是最能想到，也是最简单的方法。利用sort函数对数组进行由小到大排序，然后取前k个值入vector即可。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k == 0 || input.size() == 0) //排除特殊情况
            return res;
        sort(input.begin(), input.end()); //排序
        for(int i = 0; i < k; i++){ //因为k<=input.length,取前k小
            res.push_back(input[i]);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，sort函数属于快排
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用

方法二：堆排序

具体做法：

利用input数组中前k个元素，构建一个大小为k的大顶堆，对于后续的元素，依次比较其与堆顶的大小，若是比堆顶小，则堆顶弹出，再将新数加入堆中，直至数组结束。最后将堆顶依次弹出即是最小的k个数。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k == 0 || input.size() == 0) //排除特殊情况
            return res;
        priority_queue<int> q;  
        for(int i = 0; i < k; i++)//构建一个k个大小的堆
            q.push(input[i]);
        for(int i = k; i < input.size(); i++){
            if(q.top() > input[i]){  //较小元素入堆
                q.pop();
                q.push(input[i]);
            }
        }
        for(int i = 0; i < k; i++){ //堆中元素取出入vector
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}k\right)O(nlog\_2k)$O(nlog2​k)，构建和维护大小为k的堆，需要$lo{g}_{2}klog\_2k$log2​k，加上遍历整个数组
• 空间复杂度：$O\left(k\right)O(k)$O(k)，堆空间