[Leetcode][python]Sort Colors/颜色分类-蒲公英云

[Leetcode][python]Sort Colors/颜色分类

迷南。 2022-06-07 12:19 264阅读 0赞

题目大意

给出一个由红、白、蓝三种颜色组成的数组，把相同颜色的元素放到一起，并整体按照红、白、蓝的顺序。用0表示红色，1表示白色，2表示蓝色。这题也称为荷兰国旗问题。

解题思路

参考：
https://shenjie1993.gitbooks.io/leetcode-python/075 Sort Colors.html

三指针：如果只有两种颜色，那么很容易想到一前一后两个指针向中间遍历，颜色不对就交换位置。三种颜色仍然可以这么做，只不过要多一个指针，前后两个指针用来分隔已经排好的红色和蓝色，中间的指针来遍历元素：
如果是红色，那么和前指针交换，并两个一起向后移，前指针换过来的一定是白色的，因为中指针已经扫描过那些元素了
如果是白色，那么继续向后移
如果是蓝色，那么和后指针交换，后指针向前移，中指针不能后移，因为此时不确定换过来的元素是什么颜色

代码

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left = mid = 0
        right = len(nums) - 1
        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                left += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1