前言

今天要解的題目是 Sort Colors（排序顏色）。題目給我們一個陣列 nums，這個陣列裡包含 0、1 和 2，分別代表紅色、白色和藍色。現在要求我們將這些顏色按照紅、白、藍的順序排序。

這題的限制是不能使用內建的排序函數，因此我們需要想辦法在 O(n) 的時間內完成這個排序操作。而這個問題的經典解法是「三路快排」，也稱為荷蘭國旗問題。接下來我們來看看具體的解法吧！

題目 Sort Colors

難度：Medium

題目描述：

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（藍色）的陣列，要求將這些顏色按照紅、白、藍的順序進行排序，並且要求原地排序，即不使用額外的空間。

範例 1：

輸入： nums = [2, 0, 2, 1, 1, 0]

輸出： [0, 0, 1, 1, 2, 2]

範例 2：

輸入： nums = [2, 0, 1]

輸出： [0, 1, 2]

思路

這道題的核心解法是使用三路快排（Three-way partitioning）來將陣列中的數字分為三個部分：0 的部分、1 的部分和 2 的部分。我們用三個指針來實現這個操作，並通過掃描一次陣列，完成排序。

具體思路：

1. 三個指針：

   • left 指向應該放 0 的位置。
   • right 指向應該放 2 的位置。
   • i 用來遍歷陣列，掃描整個陣列。

2. 操作邏輯：

   • 當 nums[i] 是 0 時，將 nums[i] 和 nums[left] 交換，然後 i 和 left 同時向右移動。
   • 當 nums[i] 是 2 時，將 nums[i] 和 nums[right] 交換，然後 right 向左移動，但 i 位置暫時不動，因為交換後 i 位置的數字還需要進行處理。
   • 當 nums[i] 是 1 時，只需要將 i 向右移動。

3. 停止條件：

   • 當 i 超過 right 時，整個排序結束。

實作

function sortColors(nums: number[]): void {
    let left = 0; // 指向放 0 的位置
    let right = nums.length - 1; // 指向放 2 的位置
    let i = 0; // 用來遍歷陣列

    while (i <= right) {
        if (nums[i] === 0) {
            // 當遇到 0，將其放到 left 位置
            [nums[i], nums[left]] = [nums[left], nums[i]]; // 交換
            left++; // left 向右移動
            i++; // i 向右移動
        } else if (nums[i] === 2) {
            // 當遇到 2，將其放到 right 位置
            [nums[i], nums[right]] = [nums[right], nums[i]]; // 交換
            right--; // right 向左移動
            // i 不移動，因為交換過來的元素還需要再檢查
        } else {
            // 當遇到 1，只需要跳過
            i++;
        }
    }
}

解題心法

1. 三路快排的概念：

   • 我們用三個指針來管理三個區域：left 指向 0 的區域，right 指向 2 的區域，而中間的區域則由 1 組成。
   • 這樣的解法能夠在一次遍歷中完成對數據的分區，非常高效，能夠達到 O(n) 的時間複雜度。

2. 交換的操作：

   • 當遇到 0 時，將其與 left 位置的元素交換，這樣 left 指針向右移動，0 就被放到正確的位置。
   • 當遇到 2 時，將其與 right 位置的元素交換，然後將 right 指針向左移動，2 被放到正確的位置。
   • 當遇到 1 時，因為它本身在中間區域，不需要交換，我們只需要繼續移動 i。

3. 注意 i 和 right 的關係：

   • 每當我們交換 nums[i] 和 nums[right] 時，i 不會立即移動，因為交換過來的數字可能還需要進一步處理。

為什麼這樣處理？

這種處理方式利用了三路快排的思想，將問題分為三個區域處理，能夠在 O(n) 的時間內完成排序，同時只使用常數級別的額外空間。這是一種非常高效的解法，能夠保證我們不需要再進行額外的掃描或排序操作。

本次要點：

• 三路快排：將陣列分為三個區域，分別對應 0、1 和 2。
• 指針交換：通過交換操作，將每個元素移動到正確的區域。
• 一次遍歷：只需掃描一遍陣列，就可以完成排序操作，時間複雜度為 O(n)。

這道題是否讓你感受到三路快排的神奇呢？
學會這個技巧後，對於類似需要分區的問題，你就可以輕鬆應對了！
期待下次我們一起挑戰更多有趣的題目吧！💪🌟