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

题目分析：

本题需要实现数字只包含0,1,2的排序，并且要求一次遍历。
由于只用把数字隔离开，很容易想到快排的分割操作partition。
将三类数字隔离开，也就是模拟三路快排的分割操作了。

解题思路

快排是选取哨兵p，将一段数组分成<p，=p，>p三类，并按这个顺序隔离开。
本题类似，哨兵为1，将一段数组分成0,1,2，即<1，=1，>1，并按这个顺序隔离开。

代码如下

class Solution:

    def sortColors(self, nums: List[int]) -> None:

        left = 0

        #mid表示目前第一个1的位置，在len(nums)表示1还未出现

        #加入1的操作，只用将mid-1，然后与left交换

        mid = len(nums)

        #right表示目前第一个2的位置，在len(nums)表示第一个2还未出现

        #加入2的操作，只用将right-1，然后与left交换

        right = len(nums)

        #left是一个游标，不断交换，直到nums[left]=0

        while left < mid:

            if nums[left] == 0:

                left += 1

            elif nums[left] == 1:

                mid -= 1

                temp = nums[left]

                nums[left] = nums[mid]

                nums[mid] = temp

            elif nums[left] == 2:

                right -= 1

                temp = nums[left]

                nums[left] = nums[right]

                nums[right] = temp

                # 处理出现了2，但是还未出现1的情况

                if mid > right:

                    mid = right

巴特西

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

题目分析：

解题思路

最新文章

热门文章