剑指 Offer 40. 最小的k个数

[Tcdian]

剑指 Offer 40. 最小的k个数

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

Example 1

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

Example 2

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

Note

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

[Tcdian]

Solution

• TypeScript Solution

function getLeastNumbers(arr: number[], k: number): number[] {
    if (k === 0) {
        return [];
    }
    return quickFind(arr, 0, arr.length - 1, k);
};

function quickFind(nums: number[], left: number, right: number, target: number): number[] {
    const pivotIndex = Math.floor(Math.random() * (right - left + 1) + left);
    const pivotValue = nums[pivotIndex];
    swap(nums, pivotIndex, right);
    let separator = left - 1;
    for (let i = left; i < right; i++) {
        if (nums[i] < pivotValue) {
            swap(nums, ++separator, i);
        }
    }
    swap(nums, ++separator, right);
    if (separator === target - 1) {
        return nums.slice(0, separator + 1);
    } else if (separator < target - 1) {
        return quickFind(nums, separator + 1, right, target);
    } else {
        return quickFind(nums, left, separator - 1, target);
    }
}

function swap(nums: number[], x: number, y: number) {
    const temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}