最小的k个数

1. 题目描述

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

2. 思路分析

利用“快速排序”的中的 partition 操作：返回 index，小于 index 对应元素的元素都放在了左边，大于 index 对应元素的元素都放在右边。

利用这个特性，只要我们的 partition 返回值是 k - 1，那么数组中前 k 个元素已经被摆放到了正确位置，直接遍历输出即可。

由于不需要排序全部，整体的时间复杂度是 O(N)。但美中不足的是：要在原数组操作，除非用 O(N)的空间来做拷贝。除此之外，针对海量动态增加的数据，也不能很好处理。这种情况需要用到“最大堆”，请前往《堆》章节查看。

3. 代码实现

function partiton(arr = [], start, end) {
    const length = arr.length
    if (!length) {
        return null
    }

    let v = arr[start],
        left = start + 1,
        right = end

    while (1) {
        while (left <= end && arr[left] <= v) ++left
        while (right >= start + 1 && arr[right] >= v) --right

        if (left >= right) {
            break
        }

        ;[arr[left], arr[right]] = [arr[right], arr[left]]
        ++left
        --right
    }

    ;[arr[right], arr[start]] = [arr[start], arr[right]]
    return right
}

function getKthNumbers(nums = [], k) {
    if (k <= 0) {
        return null
    }

    const length = nums.length
    const result = new Array(k)
    let start = 0,
        end = length - 1
    let index = partiton(nums, start, end)
    while (index !== k - 1) {
        if (index > k - 1) {
            // 前k个元素在 [start, index] 下标范围内
            // 要进一步处理，缩小区间
            end = index - 1
            index = partiton(nums, start, end)
        } else {
            // [start, index]都属于小于k的元素，但不是全部
            // 剩下要处理的区间是 [index + 1, end]
            start = index + 1
            index = partiton(nums, start, end)
        }
    }

    for (let i = 0; i < k; ++i) {
        result[i] = nums[i]
    }

    return result
}

/**
 * 以下是测试代码
 */

console.log(getKthNumbers([4, 5, 1, 6, 2, 7, 3, 8], 4)) // output: [2, 3, 1, 4]
console.log(getKthNumbers([10, 2], 1))