LeetCode 75. Sort Colors （python一次遍歷，模擬三路快排）

題目分析：

本題需要實現(xiàn)數(shù)字只包含0,1,2的排序，并且要求一次遍歷。

由于只用把數(shù)字隔離開，很容易想到快排的分割操作partition。

將三類數(shù)字隔離開，也就是模擬三路快排了。

解題思路

快排是選取哨兵p，將一段數(shù)組分成<p，=p，>p三類，并按這個順序隔離開。

本題類似，哨兵為1，將一段數(shù)組分成0,1,2，即<1，=1，>1，并按這個順序隔離開。

代碼如下

class Solution: def sortColors(self, nums: List[int]) -> None:left = 0#mid表示目前第一個1的位置，在len(nums)表示1還未出現(xiàn)#加入1的操作，只用將mid-1，然后與left交換mid = len(nums)#right表示目前第一個2的位置，在len(nums)表示第一個2還未出現(xiàn)#加入2的操作，只用將right-1，然后與left交換right = len(nums)#left是一個游標(biāo)，不斷交換，直到nums[left]=0while left < mid:if nums[left] == 0:left += 1elif nums[left] == 1:mid -= 1temp = nums[left]nums[left] = nums[mid]nums[mid] = tempelif nums[left] == 2:right -= 1temp = nums[left]nums[left] = nums[right]nums[right] = temp# 處理出現(xiàn)了2，但是還未出現(xiàn)1的情況if mid > right:mid = right

總結(jié)

以上是生活随笔為你收集整理的LeetCode 75. Sort Colors （python一次遍历，模拟三路快排）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。