题目描述

输入n个整数，找出其中最小的k个数。

注意：

• 数据保证k一定小于等于输入数组的长度;
• 输出数组内元素请按从小到大顺序排序;

样例

输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

算法1

(直接排序) $O(nlogn)$

C++ 代码

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

算法2

(堆排序) $O(klogn)$

堆排序，输出前k个

C++ 代码

class Solution {
public:
    void down(vector<int>& ans, int i, int n){ // 在ans的[i,n]上维护小顶堆
        int j = 2 * i + 1; // i的左孩子
        int tmp = ans[i];
        while(j < n){
            if(j + 1 < n && ans[j] > ans[j + 1]) ++ j;
            if(tmp < ans[j]) break;
            else{
                ans[i] = ans[j];
                i = j; j = 2 * i + 1;
            }
        }
        ans[i] = tmp;
    }
    vector<int> getLeastNumbers_Solution(vector<int>& input, int k) {
        if(input.size() < k || k == 0) return {};
        int n = input.size();
        for(int i = n >> 1; i >= 0; --i)
            down(input, i, n);
        vector<int> ret;
        for(int i = n - 1; i >= n - k ; -- i){
            ret.push_back(input[0]);
            swap(input[0], input[i]);
            down(input, 0, i);
        }
        return ret;
    }
};

算法

(快速选择) $O(kn)$

快速选择算法输出前k个

C++ 代码

class Solution {
public:
    int quick_select(vector<int>& ans, int l, int r, int k) {
        if(l == r) return ans[l];
        int i = l - 1, j = r + 1, tmp = ans[l + r >> 1];
        while(i < j){
            while(ans[++i] < tmp);
            while(ans[--j] > tmp);
            if(i < j) swap(ans[i], ans[j]);
        }
        int sl = j - l + 1; // 左边的数量
        if(sl >= k) return quick_select(ans, l, j, k);
        return quick_select(ans, j + 1, r, k - sl);
    }
    vector<int> getLeastNumbers_Solution(vector<int>& input, int k) {
        if(input.size() < k || k == 0) return {};
        int n = input.size();
        vector<int> ret(k);
        for(int i = 0; i < k; ++ i) ret[i] = quick_select(input, 0, n - 1, i + 1);
        return ret;
    }
};