LeetCode Sort Colors

LeetCode解題之Sort Colors

---

原題

給出一個由紅、白、藍三種顏色組成的數組，把相同顏色的元素放到一起，並整體按照紅、白、藍的順序。用0表示紅色，1表示白色，2表示藍色。這題也稱為荷蘭國旗問題。

注意點：

盡量只遍歷一次

例子：

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

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

解題思路

如果只有兩種顏色，那麼很容易想到一前一後兩個指針向中間遍歷，顏色不對就交換位置。三種顏色仍然可以這麼做，只不過要多一個指針，前後兩個指針用來分隔已經排好的紅色和藍色，中間的指針來遍歷元素：

如果是紅色，那麼和前指針交換，並兩個一起向後移，前指針換過來的一定是白色的，因為中指針已經掃描過那些元素了 如果是白色，那麼繼續向後移 如果是藍色，那麼和後指針交換，後指針向前移，中指針不能後移，因為此時不確定換過來的元素是什麼顏色

AC源碼

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left = mid = 0
        right = len(nums) - 1
        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                left += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1


if __name__ == "__main__":
    l = [1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 0, 2]
    Solution().sortColors(l)
    assert l == [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2]