题解 | #最小的K个数#

方法一：排序

将输入的数组进行排序，取前 K个值即可

时间复杂度：O(nlong^k)

空间复杂度：O(1)

class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        vector<int> res;
        //特殊情况处理
        if (k == 0 || k > input.size())
            return res;
	  	//排序
        sort(input.begin(), input.end());

       for(int i = 0; i < k; i++) {
            res.push_back(input[i]);
       }

        return res;
    }
};

方法二：堆排序

设置一个大小为K的优先队列，将输入数组插入到优先队列中，最终就得到前K个大小的数组

时间复杂度：O(nlong^k)

空间复杂度：O(k)

class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        vector<int> res;
        //特殊情况处理
        if (k == 0 || k > input.size())
            return res;
        //大顶堆
        priority_queue<int, vector<int>> temp;

        for (int i = 0; i < input.size(); i++) {
            if (i < k)
                temp.push(input[i]);
            else {
                if (input[i] < temp.top()) {
                    temp.pop();
                    temp.push(input[i]);
                }
            }
        }

        while (!temp.empty()) {
            res.push_back(temp.top());
            temp.pop();
        }

        return res;
    }
};