[Lc]面试题40最小的k个数

题目

题解

1. 堆法

时间复杂度：$O(n\log k)$，其中 nn 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 $O(\log k)$ 的时间复杂度，最坏情况下数组里 nn 个数都会插入，所以一共需要 $O(n\log k)$ 的时间复杂度。
空间复杂度：$O(k)$，因为大根堆里最多 k 个数。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {//两个方法。1.用堆
        vector<int> res;
        if(arr.empty() || k==0) return res;//arr为空或者k为0，直接返回res
        priority_queue<int,  vector<int>> p;//定义大顶堆。（若取k个大数用小顶堆）
        int n = arr.size();
        for(int i=0; i<n; i++){//遍历数组
            if(p.size() < k){
                p.push(arr[i]);
            }//若在k以内直接把数字加入堆中
            else if(p.top() > arr[i]){
                p.pop();
                p.push(arr[i]);
            }//否则判断堆顶与现在遍历的数字的大小，若堆顶数字大则抛弃堆顶，压入新的数字，否咋抛弃该数字
        }
        for(int i=0; i<k; i++){
            res.push_back(p.top());
            p.pop();
        }//把堆中数字压入res
        return res;
    }
};

2. 快排思想

比较难理解的方法，这个方法摘自leetcode官方题解，有一些修改。

时间复杂度：期望为 $O(n)$ ，由于证明过程很繁琐，所以不再这里展开讲。具体证明可以参考《算法导论》第 9 章第 2 小节。

最坏情况下的时间复杂度为 $O(n^2)$。情况最差时，每次的划分点都是最大值或最小值，一共需要划分 $n-1$ 次，而一次划分需要线性的时间复杂度，所以最坏情况下时间复杂度为 $O(n^2)$。

空间复杂度：期望为 $O(\log n)$，递归调用的期望深度为 $O(\log n)$，每层需要的空间为 $O(1)$，只有常数个变量。

最坏情况下的空间复杂度为 $O(n)$。最坏情况下需要划分 $n$ 次，即 randomized_selected 函数递归调用最深 $n-1$ 层，而每层由于需要 $O(1)$ 的空间，所以一共需要 $O(n)$ 的空间复杂度。

class Solution {
    //这是快排里面的划分函数，即选择一个数将数组划分成左边小于该数，右边大于该数
    int partition(vector<int>& a, int low, int high){
    int key_value = a[low];//定义最右边的数为基准，因为前面已经把随机选取对的数与最左的数进行了调换
    while(low<high){
        while(low < high && a[high] >= key_value) high--;
        a[low] = a[high];
        while(low < high && a[low] <= key_value) low++;
        a[high] = a[low];
    }
    a[low] = key_value;
    return low;
}
    // 基于随机的划分
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l;//选取随机数
        swap(nums[l], nums[i]);//将其放到首位
        return partition(nums, l, r);//划分左右
    }
    void randomized_selected(vector<int>& arr, int l, int r, int k) {
        if (l >= r) return;//如果左大于右直接返回，说明有错或者递归完成
        int pos = randomized_partition(arr, l, r);//选随机数并划分左右
        int num = pos - l + 1;//num记录当前已经划分的个数
        if (k == num) return;//若个数等于k，说明前num个都是小的数，直接返回
        else if (k < num) randomized_selected(arr, l, pos - 1, k);//若k小于num，在左半段继续递归进行划分
        else randomized_selected(arr, pos + 1, r, k - num);   //若k大于num，在右半段继续递归划分
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        srand((unsigned)time(NULL));//定义随机数的种子
        randomized_selected(arr, 0, (int)arr.size() - 1, k);//调用随机选择函数，随机选一个数并完成左右的划分
        vector<int>vec;
        for (int i = 0; i < k; ++i) vec.push_back(arr[i]);
        return vec;//把k个小数返回结果
    }
};

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Contents

题目

题解

1. 堆法

2. 快排思想