Partition 搜寻第 k 个数字

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

/**
 * @param {number[]} numsList
 * @param {number} kth
 * @return {number}
 */
var findKthLargest = function(numsList, kth) {
    // 选择第 k 大的数字 ： 在排序的数字阵列中，选择 (length - k) 阵列索引的数字
    let kIndexNumber= numsList.length - kth;
    // 左指标：从阵列头开始
    let leftPointer = 0;
    // 右指标：从阵列尾开始
    let rightPointer = numsList.length - 1;
    while (leftPointer < rightPointer) {
        // 当左右指标没有交叉，继续寻找
        let partitionPointer = partitionNumberList(numsList, leftPointer, rightPointer);

        if (partitionPointer == kIndexNumber) {
            // 目前切割的点，就是要寻找的第 k 个索引的数字
            break;
        } else if (partitionPointer < kIndexNumber) {
            // 目前切割的点，比要找的 k 个索引数字还小，切割点左边确认数字更小不需要找，往切割点右边部分继续找
            // 将「左指标」移动到「切割点」右方
            leftPointer = partitionPointer + 1;
        } else {
            // 目前切割的点，比要找的 k 个索引数字还大，切割点右边确认数字更大不需要找，往切割点左边部分继续找
            // 将「右指标」移动到「切割点」左方
            rightPointer = partitionPointer - 1;
        }
    }

    return numsList[kIndexNumber];
};

// 切割数字阵列
var partitionNumberList = function(numsList, leftPointer, rightPointer) {
    // 选择右指标当作「检查数字」
    let pivotCheckNumber = numsList[rightPointer];
    // 较小数字纪录指标设定为左指标
    let smallerNumberPointer = leftPointer;

    for(let i = leftPointer; i < rightPointer; i++) {
        // 从「左指标」检查到「右指标」
        if (numsList[i] <= pivotCheckNumber) {
            // 若「目前检查的数字」小于等于「检查的数字」
            // 将目前数字放到「较小数字记录指标」位置
            [numsList[smallerNumberPointer], numsList[i]] = [numsList[i], numsList[smallerNumberPointer]];
            // 「较小数字记录指标」位置往后移动
            smallerNumberPointer++;
        }
    }
    // 检查完成，确认「较小数字记录指标」数字都比「检查数字」小
    // 「较小数字记录指标」与「检查数字」交换
    //  - 「较小数字记录指标」左方都是比「检查数字」小的数字
    //  - 「较小数字记录指标」右方都是比「检查数字」大的数字
    [numsList[smallerNumberPointer], numsList[rightPointer]] = [numsList[rightPointer], numsList[smallerNumberPointer]];

    return smallerNumberPointer;
};

function findKthSmallestNumber(numsList: number[], kth: number): any {
    // 设定指标
    let leftPointer = 0;
    let rightPointer = numsList.length - 1;

    while (leftPointer < rightPointer) {
        // 切割点
        let partitionPointer = partitionNumberList(numsList, leftPointer, rightPointer);

        if (partitionPointer == kth) {
            // 如果「切割点」刚好是第 k 个数字，不需要再找了，直接回传切割点指标数字
            break;
        }

        if (partitionPointer < kth) {
            // 如果「切割点」比第 k 个数字还要小，表示目前切割点是偏左，在 k 的左边
            // 所以左边的数字一定是比较小不用找，可能的答案在右边
            // 往右方部分找，找下一个切割点
            leftPointer = partitionPointer + 1;
        } else {
            // 如果「切割点」比第 k 个数字还要大，表示目前切割点是偏右，在 k 的右边
            // 所以右边的数字一定是比较大不用找，可能的答案在左边
            // 往左方部分找，找下一个切割点
            rightPointer = partitionPointer - 1;
        }
    }

    return numsList[kth];
}


// 切割数字阵列
var partitionNumberList = function(numsList: number[], leftPointer: number, rightPointer: number): number {
    // 选择右指标当作「检查数字」
    let pivotCheckNumber = numsList[rightPointer];
    // 较小数字纪录指标设定为左指标
    let smallerNumberPointer = leftPointer;

    for(let i = leftPointer; i < rightPointer; i++) {
        // 从「左指标」检查到「右指标」
        if (numsList[i] <= pivotCheckNumber) {
            // 若「目前检查的数字」小于等于「检查的数字」
            // 将目前数字放到「较小数字记录指标」位置
            [numsList[smallerNumberPointer], numsList[i]] = [numsList[i], numsList[smallerNumberPointer]];
            // 「较小数字记录指标」位置往后移动
            smallerNumberPointer++;
        }
    }
    // 检查完成，确认「较小数字记录指标」数字都比「检查数字」小
    // 「较小数字记录指标」与「检查数字」交换
    //  - 「较小数字记录指标」左方都是比「检查数字」小的数字
    //  - 「较小数字记录指标」右方都是比「检查数字」大的数字
    [numsList[smallerNumberPointer], numsList[rightPointer]] = [numsList[rightPointer], numsList[smallerNumberPointer]];

    return smallerNumberPointer;
};