---
title: "#75 Sort Colors"
tags: LeetCode, Top100
---
#75 Sort Colors
==

題目描述
--
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.

Here, we will use the integers ==0==, ==1==, and ==2== to represent the color red, white, and blue respectively.

Follow up:

* Could you solve this problem without using the library's sort function?
* Could you come up with a one-pass algorithm using only ==O(1)== constant space?

Example 1:
--
>Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

解題思維
--
利用two pointer去夾集出排序，達到One pass和O(1)的空間複雜度

Two Pointer
--

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        if length == 1:
            return
        left, right = 0, -1
        point = 0
        while point <= length+right:
            if nums[point] == 0:
                nums[point], nums[left] = nums[left], nums[point]
                left += 1
                point += 1
            elif nums[point] == 1:
                point += 1
            elif nums[point] == 2:
                nums[point], nums[right] = nums[right], nums[point]
                right -= 1