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