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.
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
- code, when right-=1 later, need to use i <= right in the while condition
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i, left, right = 0, 0, len(nums) - 1
while i <= right:
if nums[i] == 0:
nums[left], nums[i] = nums[i], nums[left]
left += 1
i += 1
elif nums[i] == 2:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
elif nums[i] == 1:
i += 1
- c , only difference is, when larger, -=1 at first. Then equal < large in while condition
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
smaller, equal, larger = 0, 0, len(nums)
while equal < larger:
if nums[equal] == 0:
nums[smaller], nums[equal] = 0, nums[smaller]
equal += 1
smaller += 1
elif nums[equal] == 1:
equal += 1
else: # ==2.
larger -= 1
nums[equal], nums[larger] = nums[larger], 2