Leetcode 75. Sort Colors

給定一個只有0,1,2的array,將他原地排序。

想法

(1)暴力解

重頭開始直接排序。

程式碼:

def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if(nums[i]>nums[j]):
                    tag = nums[i]
                    nums[i] = nums[j]
                    nums[j] = tag

(2) 計數排序

因為只有0,1,2三種數字,所以可以分別記錄0跟1出現的次數tag跟tag1,再將索引0到tag的值變為0,索引tag到tag+tag1的值變成1,其餘變成2。

程式碼:

def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        tag = 0
        tag1 = 0
        for i in nums:
            if(i==0):
                tag+=1
            elif(i==1):
                tag1+=1
        for i in range(len(nums)):
            if(i<tag):
                nums[i] = 0
            elif(i>=tag and i<tag+tag1):
                nums[i] = 1
            else:
                nums[i] = 2 

(3)使用兩個指標

分別記錄左,右,中間,來幫助排序。

程式碼

def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0
        right = len(nums)-1
        middle = 0
        while(right>=middle):
            if(nums[middle]==0):
                tag = nums[middle]
                nums[middle] = nums[left]
                nums[left] = tag
                left+=1
                middle+=1
            elif(nums[middle]==2):
                tag = nums[middle]
                nums[middle] = nums[right]
                nums[right] = tag
                right-=1
            else:
                middle+=1