---
# System prepended metadata

title: 75. Sort Colors
tags: [pointer, Leetcode, medium, python, array, Top 100 Liked Questions]

---

###### 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:
``` 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)
```