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

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

## 题目大意 ##

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

## 解题思路 ##

参考：  
[https://shenjie1993.gitbooks.io/leetcode-python/075 Sort Colors.html][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

## 总结 ##

[https_shenjie1993.gitbooks.io_leetcode-python_075 Sort Colors.html]: https://shenjie1993.gitbooks.io/leetcode-python/075%20Sort%20Colors.html