# leetcode: 75. Sort Colors

## Problem

```# Given an array with n objects colored red, white or blue,
# sort them 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.
#
# Note:
# You are not suppose to use the library's sort function for this problem.
#
# click to show follow up.
#
# A rather straight forward solution is a two-pass algorithm using counting sort.
# First, iterate the array counting number of 0's, 1's, and 2's,
# then overwrite array with total number of 0's,
# then 1's and followed by 2's.
# Could you come up with an one-pass algorithm using only constant space?```

## Idea

```1.由于x[:red+1]都是被white指针滑过的区域，保证了x[red]一定为0，

2.而x[blue:]尚未被white指针滑过，所以无法保证了x[blue]一定为2，

3.注意循环条件是 white <= blue 。```

## AC

```class Solution():
def sortColors(self, x):
red, white, blue = 0, 0, len(x)-1
while white <= blue:
if x[white] == 0:
x[red], x[white], white, red = x[white], x[red], white+1, red+1
elif x[white] == 1:
white += 1
else:
x[white], x[blue], blue = x[blue], x[white], blue-1

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

600 篇文章44 人订阅

0 条评论

## 相关文章

Given a non-negative integer num, repeatedly add all its digits until the resul...

1995

1955

1953

3714

3755

1012

36211

1637

### FZU 1064 教授的测试（卡特兰数，递归）

Problem 1064 教授的测试 Accept: 149 Submit: 364 Time Limit: 1000 mSec Memor...

3628

1161