剑指Offer题解 - Day37

剑指 Offer 40. 最小的 k 个数

力扣题目链接 (opens new window)

输入整数数组 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

思路：

首先考虑使用暴力破解进行题解。思路就是将数组排序后，截取前k个数并返回即可。

暴力法

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
const getLeastNumbers = (arr, k) => {
    return arr.concat().sort((a, b) => a - b).slice(0, k)
};

分析：

暴力法纯粹就是使用数组的API。不建议在面试中使用本方法。只作为一种思路即可。

快排

上述方法中，我们直接使用了数组提供的排序方法sort 。这里我们使用快排来实现排序。

按照题目的要求，只需要将数组划分为 最小的 k个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。

我们的核心思路就是哨兵划分后，判断哨兵在数组中的索引是否等于 k ****。因为索引等于k，意味着哨兵左边所有的数都比哨兵小，也就是最小的k个数。

下面就来实现代码：

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
const quickSort = (arr, k, l, r) => {
    if (l >= r) return;
    let i = l;
    let j = r;
    while(i < j) {
        while(i < j && arr[j] >= arr[l]) j--;
        while(i < j && arr[i] <= arr[l]) i++;
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    [arr[l], arr[i]] = [arr[i], arr[l]];
    if (i > k) quickSort(arr, k, l, i - 1);
    if (i < k) quickSort(arr, k, i + 1, r);
    return arr.slice(0, k);
}

const getLeastNumbers = (arr, k) => {
    if (k >= arr.length) return arr; // 如果k大于等于目标数组长度，则直接返回数组
    return quickSort(arr, k, 0, arr.length - 1); // 开始快排
};

• 时间复杂度 O(N)。
• 空间复杂度 O(logN)。

分析：

首先看主函数内的逻辑。如果k大于等于数组长度，意味着最小的k个数就是数组本身，直接返回数组即可。

然后进入快排函数的逻辑，这里与平常的快排不同之处在于，需要额外快递一个参数k，用来判断快排过程中，哨兵的位置和k的关系。

接下来就是快排的逻辑，这里就不做分析了，具体可以看上上篇的题解。直接快进到交换哨兵位置下一步。交换完哨兵，此时数组被哨兵划分为两部分，前半部分的值小于哨兵，后半部分的值大于哨兵。

此时需要判断哨兵位置与k的关系。如果哨兵位置大于k，意味着前k个最小数处于左子数组，此时需要继续递归快排左子数组；如果哨兵位置小于k，意味着前k个最小数的一部分处于右子数组，此时需要继续递归快排右子数组；如果哨兵位置等于k，意味着哨兵左侧的数组就是前k个最小数。此时直接截取返回数组的前k个值即可。

总结

本题考查排序的算法。我们可以使用数组提供的排序算法，也可以自己实现排序算法。这里采用了快排的排序算法来求出最终解。因为快排里的哨兵划分跟本题十分契合，可以合理利用。

复杂度方面，对于长度为 N 的数组执行哨兵划分操作的时间复杂度为 O(N)；划分函数的平均递归深度为 O(log N) 。