Share My Python O(n) Solution


  • 0
    M

    Since it only contains three colors, we can do it like this.

    class Solution:
        ### 75. Sort Colors ###
        # @param {integer[]} nums
        # @return {void} Do not return anything, modify nums in-place instead
        def sortColors(self, nums):
            head, tail = 0, len(nums)-1
            l, r = head, tail
            while head <= tail:
                while head <= tail:
                    if nums[head] == 0:
                        nums[l] = nums[head]
                        l += 1
                        head += 1
                    elif nums[head] == 1:
                        head += 1
                    else: break
                while head <= tail:
                    if nums[tail] == 2:
                        nums[r] = nums[tail]
                        r -= 1
                        tail -= 1
                    elif nums[tail] == 1:
                        tail -= 1
                    else: break
                if head > tail: break
                tmp = nums[head]
                nums[l] = nums[tail]
                nums[r] = tmp
                l += 1
                r -= 1
                head += 1
                tail -= 1
            nums[l:r+1] = [1] * (r-l+1)
    
            return

Log in to reply
 

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