Two AC solutions in Python


  • 0
    H

    The first one is general, using Hoare partition.

    class Solution(object):
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            def Hoare_partition(nums, l, r):
                '''
                apply Hoare partition to nums[l:r]
                '''
                if l >= r-1:  return    # no more than 1 elements
                i, j = l+1, r-1
                while i <= j:
                    while i < r and nums[i] < nums[l]:    i += 1
                    while j > l and nums[j] > nums[l]:    j -= 1
                    if i < j:
                        nums[i], nums[j] = nums[j], nums[i]
                        i, j = i+1, j-1
                    elif i == j:    break
                nums[l], nums[j] = nums[j], nums[l]
                Hoare_partition(nums, l, j)
                Hoare_partition(nums, j+1, r)
                return
            
            n = len(nums)
            Hoare_partition(nums, 0, n)
            return
    

    The second is a more specific solution.

    class Solution(object):
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            
            n = len(nums)
            r, w, b = 0, 0, n-1  # we use r to track right boundary of red, w to track right boundary of white and b to track left boundary of blue
            while w <= b:
                if nums[w] == 0:
                    nums[r], nums[w] = nums[w], nums[r]
                    r, w = r+1, w+1
                elif nums[w] == 1:
                    w = w+1
                else:   # nums[w] == 2
                    nums[w], nums[b] = nums[b], nums[w]
                    b = b-1
            return
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.