LeetCode 筆記 - 75. Sort Colors

Posted on

題目在此 75. Sort Colors

給定一個只包含 0、1 和 2 的陣列，請將陣列中的元素原地排序，使得相同的元素相鄰，且按照 0、1、2 的順序排列。你必須在不使用內建排序函式的情況下完成此任務。

解題思維

因為這題的數值只有 0、1 和 2，所以千萬不要跳下去實作排序，這樣會浪費很多時間。
在這裡有個 $O(n)$ 的解法，稱為「荷蘭國旗問題」（Dutch National Flag Problem），這個方法使用三個指標來分別追蹤 0、1 和 2 的位置。

我們使用 left、mid 和 right。初始時，left 和 mid 指向陣列的起始位置，right 指向陣列的末尾位置。

  • 當 nums[mid] == 0 時，將 nums[mid] 與 nums[left] 交換，然後將 left 和 mid 向右移動一位。
  • 當 nums[mid] == 2 時，將 nums[mid] 與 nums[right] 交換，然後將 right 向左移動一位（注意這時候 mid 不動，因為交換過來的數字還沒檢查過）。
  • 當 nums[mid] == 1 時，直接將 mid 向右移動一位。

根據第二點，在 交換 nums[mid] 和 nums[right] 時，因為我們不知道從 nums[right] 交換過來的數字是什麼，所以我們不移動 mid 指標，這樣可以確保我們會再次檢查這個位置的數字，避免漏掉任何需要處理的數字。
所以終止條件會是 mid 超過 right。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def sortColors(self, nums: List[int], left: int = -1, right: int = -1) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # step 1: use two pointer and mid pointer
        # step 2: left, mid init as 0, right init as len(nums) - 1
        # step 3: if nums[mid] == 0: swap wtih left, mid move on, left move on
        #       elif nums[mid] == 2: swap wtih right, right move on (because we do not know what value come form nums[right], so we do not need to move mid pointer)
        #         otherwise, mid move on

        # time complexity: O(n)
        # space complexity: O(1)

        left, mid, right = 0, 0, len(nums) - 1

        while mid <= right:
            if nums[mid] == 0:
                nums[left], nums[mid] = nums[mid], nums[left]
                left += 1
                mid += 1
            elif nums[mid] == 2:
                nums[right], nums[mid] = nums[mid], nums[right]
                right -= 1
            else:
                mid += 1

也許你也會想看看