'''
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.
'''
from typing import List
from collections import Counter
def sort_colors0(nums: List[int]) -> None:
def particion(beg, end, left):
i = beg
j = end
while True:
while i < j and nums[i] == left:
i += 1
while i < j and nums[j-1] != left:
j -= 1
if i == j:
break
nums[i], nums[j-1] = nums[j-1], nums[i]
return i
mid = particion(0, len(nums), 0)
particion(mid, len(nums), 1)
def sort_colors1(nums: List[int]) -> None:
c = Counter(nums)
for i in range(len(nums)):
nums[i] = 0 if i < c[0] else 1 if i < c[0] + c[1] else 2
def sort_colors2(nums: List[int]) -> None:
c = Counter(nums)
for i in range(c[0]):
nums[i] = 0
for i in range(c[0], c[0]+c[1]):
nums[i] = 1
for i in range(c[0]+c[1], len(nums)):
nums[i] = 2
input_nums = [2,2,0,2,1,1,0,2]
for sort_colors in sort_colors0, sort_colors1, sort_colors2:
nums = input_nums[:]
sort_colors(nums)
print(nums)
