Leetcode: Sort colors
Given an array nums
with n
colored objects, sort the array in place so that the colors are orders. The colors are represented by the numbers 0
, 1
, and 2
.
The easiest way to achieve this is via quicksort in O(n*log n)
.
from typing import List, Optional
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
self.quicksort(nums, 0, len(nums) - 1)
def quicksort(self, arr, left, right):
if left < right:
partition_pos = self.partition(arr, left, right)
self.quicksort(arr, left, partition_pos - 1)
self.quicksort(arr, partition_pos + 1, right)
def partition(self, arr, left, right):
i = left
j = right - 1
pivot = arr[right]
while i < j:
while i < right and arr[i] < pivot:
i += 1
while j > left and arr[j] >= pivot:
j -= 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
if arr[i] > pivot:
arr[i], arr[right] = arr[right], arr[i]
return i
if __name__ == '__main__':
s = Solution().sortColors
# print(s([2,0,2,1,1,0]), [0,0,1,1,2,2])
l = [2,0,1]
print(s(l), [0,1,2])
print(l)