物歸原位 顏色排序 Sort Colors _Leetcode #75 雙指針應用

Mika Baumeister on Unsplash

題目敘述 Sort Colors

給定一個色彩陣列，裡面的顏色包含0紅色,1白色,2藍色。

要求我們透過in-place操作，把色彩陣列依序從左到右排好，
依序出現的是紅色、白色、藍色。

題目限制不可以使用內建的sort function。

測試範例

Example 1:

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

Example 2:

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

約束條件

Constraints:

• n == nums.length

n 代表輸入陣列的長度。

• 1 <= n <= 300

n介於1~300之間。

• nums[i] is either 0, 1, or 2.

 每個陣列元素的值只有三種可能: 0(紅色), 1(白色), 2(藍色)

.

進階提問

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

能不能想出一次線性掃描，並且只使用常數空間的演算法?

演算法 雙指針 + swap操作

總共只有三個顏色。

根據題意，紅色必須放在左邊那個區域，白色置中，藍色放在右邊那個區域。

可以用雙指針，分別指向頭部(放置紅色的目標區域)和尾部(放置藍色的目標區域)。

遇到紅色就把它放到頭部靠左邊的位置，透過置換元素操作in-place完成。

遇到藍色就把它放到尾巴靠右邊的位置，透過置換元素操作in-place完成。

(實作上的細節是，藍色和尾巴元素交換後，必須多檢查一次，確保間換過來的顏色也是放在正確的區域)

最後留在中間，自然就是的白色。

程式碼 雙指針 + swap操作

class Solution:
    
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # constant for colors
        RED, WHITE, BLUE = 0, 1, 2
        
        # two pointers for RED as well as BLUE
        idx_red, idx_blue = 0, len(nums)-1
        
        i = 0
        while i <= idx_blue :
            
            if nums[i] == RED:
                
                nums[idx_red], nums[i] = nums[i], nums[idx_red]
                
                # update idx for red
                idx_red += 1

            elif nums[i] == BLUE:
            
                nums[idx_blue], nums[i] = nums[i], nums[idx_blue]
                
                # update idx for blue
                idx_blue -= 1
                
                # i-1 in order to stay and do one more color check on next iteration
                i -= 1

            # i move forward
            i += 1                
        

複雜度分析

時間複雜度: O(n)

從左到右一次線性掃描，每個元素檢查一次，放置到對應的顏色區域。

空間複雜度: O(1)

使用到的都是固定此吋的臨時變數，為常數級別O(1)。

關鍵知識點 指針 + in-place搬移元素的技巧

這題用到的是in-place搬移元素的技巧，

和之前學過的Move Zeros很像，都是鑲在目標區域建立指針，
接著掃描每個元素，把每個元素搬到對應的區域。

Reference

[1] Sort Colors - LeetCode