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

  • 对于一个给定无序数组,返回最小的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(nlog2n)O(nlog_2n)O(nlog2n),sort函数属于快排
  • 空间复杂度:O(1)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(nlog2k)O(nlog_2k)O(nlog2k),构建和维护大小为k的堆,需要log2klog_2klog2k,加上遍历整个数组
  • 空间复杂度:O(k)O(k)O(k),堆空间