剑指 Offer 40 最小的k个数

Tag: 剑指-Offer Posted on 2022-02-26 14:06:55 Edited on 2022-02-26 17:17:57 Views: 313

概述

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

类似题目,求第 k 大的数: https://leetcode.com/problems/kth-largest-element-in-an-array/

labuladong 也有讲:https://labuladong.gitee.io/algo/4/31/128/

排序法

升序排序后返回前 k 个即可。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        vector<int> ans;
        k --;
        while (k >= 0) {
            ans.push_back(arr[k--]);
        }
        return ans;
    }
};

O(nlogn) 的时间复杂度。 快排需要 O(logn) 的栈空间,因此空间复杂度 O(logn)。

借鉴快排的思想

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/

时间复杂度:期望为 O(n)O(n) ,由于证明过程很繁琐,所以不在这里展开讲。具体证明可以参考《算法导论》第 9 章第 2 小节。 最坏情况下的时间复杂度为 O(n^2)。 情况最差时,每次的划分点都是最大值或最小值,一共需要划分 n - 1n−1 次,而一次划分需要线性的时间复杂度, 所以最坏情况下时间复杂度为 O(n^2)

空间复杂度:期望为 O(logn),递归调用的期望深度为 O(logn),每层需要的空间为 O(1),只有常数个变量。 最坏情况下的空间复杂度为 O(n)。 最坏情况下需要划分 n 次,即 randomized_selected 函数递归调用最深 n - 1 层, 而每层由于需要 O(1) 的空间,所以一共需要 O(n) 的空间复杂度。

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

    void helper(vector<int>& arr, int k, int l, int r) {
        if (l >= r) return;
        int p = partition(arr, l, r);
        if (p == k) {
            return;
        } else if (p > k) {
            helper(arr, k, l, p - 1);
        } else {
            helper(arr, k, p + 1, r);
        }
    }

    int partition(vector<int>& arr, int l, int r) {
        int p = arr[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; j ++) {
            if (arr[j] <= p) {
                i ++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i+1], arr[r]);
        return i + 1;
    }
};

最小堆

最小堆,压入所有元素后弹出 k 个即可。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (auto n : arr) minHeap.push(n);
        vector<int> ans;
        for (int i = 0; i < k; i ++) {
            ans.push_back(minHeap.top());
            minHeap.pop();
        }
        return ans;
    }
};

时间复杂度:O(nlogn),因为我们把 n 个元素都插入了,每次插入 O(logn)

空间复杂度:O(n)

最大堆

实际上用最大堆也是可以的哦,而且更高效。

我们这里用了 top(),需要检查 heap 是否为空,其仅在 k 为 0 时可以为空,所有需要对 k == 0 的情况进行特殊处理。

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

时间复杂度:O(nlogk),最坏情况下我们插入 n 个元素,每次插入 O(logk)

空间复杂度:堆中最多有 k 个元素,所以是 O(logk)

未经允许,禁止转载,本文源站链接:https://iamazing.cn/