Python count sort and one pass sort.


  • 2
    C
    # count sort    
    def sortColors1(self, nums):
        c0 = c1 = c2 = 0
        for num in nums:
            if num == 0:
                c0 += 1
            elif num == 1:
                c1 += 1
            else:
                c2 += 1
        nums[:c0] = [0] * c0
        nums[c0:c0+c1] = [1] * c1
        nums[c0+c1:] = [2] * c2
       
    # one pass 
    def sortColors(self, nums):
        # zero and r record the position of "0" and "2" respectively
        l, r, zero = 0, len(nums)-1, 0
        while l <= r:
            if nums[l] == 0:
                nums[l], nums[zero] = nums[zero], nums[l]
                l += 1; zero += 1
            elif nums[l] == 2:
                nums[l], nums[r] = nums[r], nums[l]
                r -= 1
            else:
                l += 1

  • 0
    J

    Nice, the one pass is far more elegant than my code below, which is inspired by quicksort...

    class Solution:
    # @param {integer[]} nums
    # @return {void} Do not return anything, modify nums in-place instead.
    def sortColors(self, nums):
        lo,hi = 0, len(nums)-1
        lo2,hi2 = 0, len(nums)-1# pointing at items that are 1
        while 1:
            while lo<len(nums) and nums[lo]!=2:
                if nums[lo]==0: 
                    if lo2<lo and nums[lo2]==1:#if there is a 1 to the left of lo
                        nums[lo],nums[lo2] = nums[lo2],nums[lo]
                        while nums[lo2]!=1: lo2+=1
                elif nums[lo]==1: 
                    if lo2<len(nums) and nums[lo2]!=1: lo2 = lo
                lo+=1
            while hi>=0 and nums[hi]!=0:
                if nums[hi]==2: 
                    if hi2>hi and nums[hi2]==1:#if there is a 1 to the right of hi
                        nums[hi],nums[hi2] = nums[hi2],nums[hi]
                        while nums[hi2]!=1: hi2-=1
                elif nums[hi]==1: 
                    if lo2<len(nums) and  nums[hi2]!=1: hi2 = hi
                hi-=1
            if hi>lo and nums[lo]==2 and nums[hi]==0:
                nums[lo],nums[hi] = nums[hi],nums[lo]
            if hi<=lo: break

Log in to reply
 

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