剑指offer-最小的K个数

本文为剑指 offer 系列第四篇。
本题比较常见，而且思路也非常清晰，一个是排序，一个用最小堆。

题目描述

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

解题思路

思路1

直接从小到大将所有所有数字进行排序，然后取前K个即可。

思路2

把所有的数据进行处理构造最小堆，然后取出前K个返回即可。

解题代码

思路1代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k>input.size()) return {};
        sort(input.begin(),input.end());
        return vector<int>(input.begin(),input.begin()+k);
    }
};

时间复杂度为O(nlogn),空间复杂度为O(n)

思路2代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k>input.size()) return {};
        priority_queue<int, vector<int>, greater<int> > q;
        for(auto a:input){
            q.push(a);
        }
        vector<int> res;
        while(k>0){
           res.push_back(q.top());
           q.pop();
           k--;
        }
        return res;
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！