###### tags: `Leetcode` `medium` `pointer` `array` `python` `Top 100 Liked Questions`

# 75. Sort Colors

## [題目連結:] https://leetcode.com/problems/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.

We will use the integers ```0, 1, and 2``` to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

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

**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]

## 解題想法:
* 題目要求將球依序0-1-2擺放
* in-place
* space: O(1)
* 0:red
* 1:white
* 2:blue
* 用三個pointer維護:
* cur_pos = 0
* 當前位置
* forTwo_pos = len(nums)-1
* 該位置以**右**都為2
* forOne_pos = 0
* 該位置以**左**都為0
* 判斷當前**cur_pos指到的值**
* 終止條件為**cur_pos已超過forTwo_pos**
* 若為2 :則與forTwo_pos的值交換 then forTwo_pos-1
* 若為0 :則與forOne_pos的值交換 then forOne_pos+1、**cur_pos+1**
* 若為1 :則cur_pos+1

## Python:

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        #用三個pointer維護
        cur_pos = 0 #當前位置
        forTwo_pos = len(nums)-1 #該位置以右都為2
        forOne_pos = 0 #該位置以左都為0
        while cur_pos<=forTwo_pos:
            if nums[cur_pos]==2:
                nums[cur_pos],nums[forTwo_pos]=nums[forTwo_pos],nums[cur_pos]
                forTwo_pos-=1
            elif nums[cur_pos]==0:
                nums[cur_pos],nums[forOne_pos]=nums[forOne_pos],nums[cur_pos]
                forOne_pos+=1
                cur_pos+=1
            else:
                cur_pos+=1
    
if __name__ == '__main__':
    result = Solution()
    nums = [2,0,2,1,1,0]
    ans = result.sortColors(nums)
    print(nums)