• 原题连接： JZ40 最小的K个数

思路1：排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        sort(input.begin(), input.end());
        for (int i = 0; i < k; ++i) res.push_back(input[i]);
        return res;
    }
};

• 时间复杂度：O(nlogn)，空间复杂度：O(n)

思路2：堆

#include <queue>
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res(k, 0);
        if (k == 0) return res;

        priority_queue<int> heap;
        for (int i = 0; i < k; ++i) heap.push(input[i]);

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

        for (int i = 0; i < k; ++i) {
            res[i] = heap.top();
            heap.pop();
        }

        return res;
    }
};

思路3：快速选择

class Solution {
public:
    vector<int> quickSort(vector<int>& arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[l]);
        if (i > k) return quickSort(arr, k, l, i-1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        vector<int> res;
        res.assign(arr.begin(), arr.begin() + k);
        return res;
    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k >= input.size()) return input;
      	// 搜索并返回最小的 
      k 个数
        return quickSort(input, k, 0, input.size()-1);
    }

};

-时间复杂度：O(n)，空间复杂度：O(logn)

😿😿😿😿😿😿