剑指Offer2 40

剑指OFFER2 面试题40 [简单]

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

方法1： 排序

很直接的思路是对原数组从小到大排序后取出前 k 个数即可。
排序可使用库函数，懒到不想写快排。

Code

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

复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
空间复杂度:O(logn)，排序所需额外的空间复杂度为 O(logn)。

方法2：大根堆

大根堆，用一个大根堆实时维护数组的前 k 个较小值
首先将前 k 个数插入大根堆中，
随后从第 k+1 个数开始遍历

具体步骤：
如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历的数。如果当前遍历到的数比大根堆的堆顶的数要大，继续往下遍历。

最后将大根堆里的数存入数组返回即可。
C++ 语言中的堆（即优先队列）为大根堆。

Code

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int>vec(k, 0);
        if (k == 0) return vec; // 排除 0 的情况
        priority_queue<int>Q;
        for (int i = 0; i < k; ++i) Q.push(arr[i]);
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

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