🔗 🟡 75. Sort Colors

tags: 陣列(Array) 排序(Sorting) 雙指針(Two Pointers)

題意

給定一個長度為 nn 的陣列 numsnums，分別代表 nn 個物品，這些物品顏色分別為紅色、白色或藍色，請 原地 對它們進行排序，使得相同顏色的物品相鄰，且按照紅色、白色和藍色的順序排列。

我們用整數 00、11 和 22 來分別代表紅色、白色和藍色。

你必須在不使用 library 的排序函數的情況下解決這個問題。

後續問題(Follow-up)

  • 你能想出一個只使用常數額外空間的單次掃描演算法嗎？

思路：雙指針(Two Pointers)

首先確定核心思路，由於只有三個數字，因此當我們將 00 放到前面、22 放到後面後，剩下的 11 自然而然地會留在中間。

因此可以使用 雙指針(Two Pointers) 來解決這個問題。分別令 l 和 r 指向下一個 00 和 22 的位置，並初始化一個指針 idx 用來遍歷陣列。以此確保在遍歷的過程中，<l< l 的位置皆為 00 ，>r> r 的位置皆為 22 。

接著根據 nums[idx] 的值，判斷是否需要將 nums[idx] 放到 l 或 r 中，以及將 idx 向右移動。

  1. 若 nums[idx] 為 00 ，則將 nums[l] 和 nums[idx] 交換，並將 l 和 idx 向右移動。
  2. 若 nums[idx] 為 22 ，則將 nums[r] 和 nums[idx] 交換，並將 r 向左移動。這裡需要注意的是，由於交換後 idx 指向的新數字有可能還是 22，因此 idx 不應移動。
  3. 若 nums[idx] 為 11 ，則將 idx 直接向右移動即可。

由於 >r> r 的位置皆為 22 ，因此終止條件為 idx > r 。

當遍歷整個陣列後，所有的 00 會被移到左邊，22 被移到右邊，因此剩下的 11 自然會留在中間，達到排序的目的。這個思路與 3-Way QuickSort 相同。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n) ，其中 nn 是陣列的長度。
  • 空間複雜度：O(1)\mathcal{O}(1) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        l, r, idx = 0, n-1, 0
        while idx <= r:  # 小於 l 的位置都是 0，大於 r 的位置都是 2
            if nums[idx] == 0:  # 把 0 放到前面
                nums[l], nums[idx] = nums[idx], nums[l]
                l += 1
                idx += 1
            elif nums[idx] == 2:  # 把 2 放到後面，這裡要注意交換來的數字可能是 2，因此 idx 不能 +1
                nums[r], nums[idx] = nums[idx], nums[r]
                r -= 1
            else:
                idx += 1
        return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1, idx = 0;
        while (idx <= r) {
            if (nums[idx] == 0)
                swap(nums[l++], nums[idx++]);
            else if (nums[idx] == 2) // 注意這裡 idx 不能 +1
                swap(nums[r--], nums[idx]);  
            else
                idx++;
        }
    }
};

參考資料

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant, colors, backlight, bright, soft lighting, dreamy atmosphere, orange tone, (1girl, solo), long hair, looking at viewer, gentle smile, bangs, black hair, brown eyes, standing, sleeveless, indoors, blunt bangs, bag, sleeveless dress, handbag, dress, (orange dress), in the library, library, bookshelves, warm light filtering through windows, cozy ambiance, soft shadows, detailed background, vintage decor, scattered books, wooden furniture