> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/bu-chong-2140-dao/75.-sort-colors.md).

# 75. Sort Colors

\# Medium

{% hint style="info" %}
Key idea:

`2` must be the end, `0` must be the begining.

Record the index of next possible `0` as `p0`; record the index of next possible `2` as `p2`.
{% endhint %}

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MHxEtotOjs_NSI31Tu2%2F-MHxF0rBMrR992Ff6Zcl%2F1600902920631.jpg?alt=media\&token=860374e7-4b46-453e-8af8-7a6cea4e31e9)

### Solution:

1. if `nums[i] = 0`, swap(nums\[p0], nums\[i]), p0 and i move forward one step
2. if `nums[i] = 2`, swap(nums\[i], nums\[p2]), p2 move back one step
3. if `nums[i] = 1`, only i move forward one step

```python
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p0 = 0
        i = 0
        p2 = len(nums) - 1
        while i <= p2:
            if nums[i] == 0:
                nums[i] = nums[p0]
                nums[p0] = 0
                p0 += 1
                i += 1
            elif nums[i] == 2:
                nums[i] = nums[p2]
                nums[p2] = 2
                p2 -= 1
            else:
                i += 1
                
        return nums
```

{% hint style="danger" %}
最难想的是`nums[i] = 1`该怎么处理，跳过即可，但是不能挪`p0`指针
{% endhint %}

Time complexity = $$O(n)$$ , space complexity = $$O(1)$$&#x20;