215. Kth Largest Element in an Array

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

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

/**
 * @param {number[]} numsList
 * @param {number} kth
 * @return {number}
 */
var findKthLargest = function(numsList, kth) {
    // 排序数字列（小到大排序）
    numsList.sort(function(a, b) {
        return a - b;
    });

    // 越后面数字越大，从后面找第 k 排名的数字
    let kthNumber = numsList[numsList.length - kth];

    return kthNumber;
};

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;
};