75. Sort Colors

Leetcode 問題: 75. Sort Colors
Categories:
Tags:

題目

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

傳入一整數陣列，不需回傳任何資料，直接修改傳入的整數陣列

傳入的整數陣列數字限定只有 0, 1, 2，將傳入的整數陣列依照大小排序（不可以用內建的排序函式庫）

Example

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Input: nums = [2,0,1]
Output: [0,1,2]

答案

索引位置 0 1 2 3 4 5
數字 2 0 2 1 1 0
檢查指標 V
分割指標 左指標 右指標

JavaScript

  1. 設定 左指標：0、右指標：整數陣列長度 -1，檢查指標：0
    • 確保 左指標 左邊數字都是 0
    • 確保 右指標 右邊數字都是 2
  2. 當 檢查指標 遇到 數字 0，將 檢查指標數字 與 左指標數字 交換
    • 左指標 一定會變成 0，然後再移動 左指標 到下一個預計放 數字 0 的位置
  3. 當 檢查指標 遇到 數字 2，將 檢查指標數字 與 右指標數字 交換
    • 右指標 一定會變成 2，然後再移動 右指標 到下一個預計放 數字 2 的位置
    • 現在 檢查指標的數字 是來自 右指標，所以可能是 0 或 1 ，需要再重新檢查
    • 檢查指標 每次都會往右移動，為了能夠再檢查一次，必須先將 檢查指標減 1，讓 檢查指標 可以重新再檢查一次
  4. 移動 檢查指標 到下一個要檢查的位置
/**
 * @param {number[]} numsList
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(numsList) {
    // 左指標
    let leftPointer = 0;
    // 右指標
    let rightPointer = numsList.length - 1;
    // 檢查指標
    let checkPointer = 0;

    while (checkPointer <= rightPointer) {
        // 當檢查指標還在右指標前面，表示還沒檢查完所有數字
        if (numsList[checkPointer] == 0) {
            // 當「檢查指標」遇到 0，「檢查指標」數字與「左指標」數字交換
            [numsList[leftPointer], numsList[checkPointer]] = [numsList[checkPointer], numsList[leftPointer]];
            // 左指標左邊確認一定都是 0，往右移動
            leftPointer++;
        } else if (numsList[checkPointer] == 2) {
            // 當「檢查指標」遇到 2，「檢查指標」數字與「右指標」數字交換
            [numsList[rightPointer], numsList[checkPointer]] = [numsList[checkPointer], numsList[rightPointer]];
            // 右指標右邊確認一定都是 2，往左移動
            rightPointer--;
            // 檢查指標維持不變，因為交換到檢查指標的數字可能是 1 或 0，所以需要重新檢查一次
            checkPointer--;
        }

        // 移動到下一個檢查指標
        checkPointer++;
    }

};

參考資料