# LeetCode 75，90%的人想不出最佳解的简单题

## 桶排序

class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
bucket = [0 for _ in range(3)]
for i in nums:
bucket[i] += 1

ret = []
for i in range(3):
ret += [i] * bucket[i]

nums[:] = ret[:]


## two pointers

class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l, r = 0, len(nums)-1
i = 0
while i < len(nums):
if i > r:
break
# 如果遇到0，则和左边交换
if nums[i] == 0:
nums[l], nums[i] = nums[i], nums[l]
l += 1
# 如果遇到2，则和右边交换
# 交换之后i需要-1，因为可能换来一个0
elif nums[i] == 2:
nums[r], nums[i] = nums[i], nums[r]
r -= 1
continue
i += 1


## 维护区间

class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 记录0，1和2的末尾位置
zero, one, two = -1, -1, -1
n = len(nums)
for i in range(n):
# 如果摆放0
# 那么1和2都往后平移一位，让一个位置出来摆放0
if nums[i] == 0:
nums[two+1] = 2
nums[one+1] = 1
nums[zero+1] = 0
zero += 1
one += 1
two += 1
elif nums[i] == 1:
nums[two+1] = 2
nums[one+1] = 1
one += 1
two += 1
else:
nums[two+1] = 2
two += 1