剑指 Offer 40. 最小的k个数

本文主要是介绍剑指 Offer 40. 最小的k个数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

不过式写法

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> result;
        int t = 0;
        for (int i = 0; i < k; i++) {
            for (int j = i+1; j < arr.size(); j++) {
                if (arr[i] > arr[j]) {
                    t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
            result.push_back(arr[i]);
        }
        return result;
    }
};

偷懒式写法

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        return vector(arr.begin(), arr.begin()+k);
    }
};

计数加隐式排序写法

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector <int> result;
        map <int, int> counts;
        if (k == 0) {
            return result;
        }
        for (auto a: arr) {
            counts[a]++;
        }
        for (auto it: counts) {
            for (int i = 0; i < it.second; i++) {
                result.push_back(it.first);
                if (result.size() == k) {
                    return result;
                }
            }
        }
        return result;
    }
};

提前中止式快排

题解参考：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/，大佬太强了，把快排说得好清楚，代码瞬间看懂

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> result;
        if (k == 0) {
            return result;
        }
        else if (k >= arr.size()) {
            return arr;
        }
        else {
            quick_sort(arr, k, 0, arr.size()-1);
            result.assign(arr.begin(), arr.begin()+k);
            return result;
        }
    }
    
    void quick_sort(vector<int>& arr, int k, int left, int right) {
        int i = left, j = right;
        while(i<j) {
            for(; i < j && arr[j] >= arr[left]; j--);
            for(; i < j && arr[i] <= arr[left]; i++);
            swap(arr[i], arr[j]);
        }
        swap(arr[i], arr[left]);
        if (i == k) {
            return;
        }
        else if (i < k) {
            quick_sort(arr, k, i+1, right);
        }
        else {
            quick_sort(arr, k, left, i-1);
        }
    }
};

堆/优先队列

注意只需要维护长度为k的堆即可（不属于前k小的元素，要么会变成堆的根，要么是在第k之后的元素），考虑到返回的是vector，我这里使用了make_heap技巧而不是priority_queue，并且这样只需要对队列头进行赋值，省去了入队出队的操作。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> result;
        if (k == 0) {
            return result;
        }
        else if (k >= arr.size()) {
            return arr;
        }
        else {
            result.assign(arr.begin(), arr.begin()+k);
            make_heap(result.begin(), result.end());
            for (int i = k; i < arr.size(); i++) {
                if (arr[i] < result[0]) {
                    result[0] = arr[i];
                    make_heap(result.begin(), result.end());
                }
            }
            return result;
        }
    }  
};

就是时间上太慢了，试了一下，还是优先队列香

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> result;
        if (k == 0) {
            return result;
        }
        else if (k >= arr.size()) {
            return arr;
        }
        else {
            priority_queue<int> Q;
            for (int i = 0; i < k; Q.push(arr[i]),i++);
            for (int i = k; i < arr.size(); i++) {
                if (arr[i] < Q.top()) {
                    Q.pop();
                    Q.push(arr[i]);
                }
            }
            while(!Q.empty()) {
                result.push_back(Q.top());
                Q.pop();
            }
            return result;
        }
    }  
};

这篇关于剑指 Offer 40. 最小的k个数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！