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