0075. 颜色分类.md

0075. 颜色分类

• 标签：数组、排序、双指针
• 难度：中等

题目大意

给定一个数组 nums，元素值只有 0、1、2，分别代表红色、白色、蓝色。将数组进行排序，使得 红色在前，白色在中间，蓝色在最后。

要求不使用标准库函数，同时仅用常数空间，一趟扫描解决。

解题思路

使用两个指针 left，right，分别指向数组的头尾。left 表示当前处理好红色元素的尾部，right 表示当前处理好蓝色的头部。

再使用一个下标 index 遍历数组，如果遇到 nums[index] == 0，就交换 nums[index] 和 nums[left]，同时将 left 右移。如果遇到 nums[index] == 2，就交换 nums[index] 和 nums[right]，同时将 right 左移。

直到 index 移动到 right 位置之后，停止遍历。遍历结束之后，此时 left 左侧都是红色，right 右侧都是蓝色。

注意：移动的时候需要判断 index 和 left 的位置，因为 left 左侧是已经处理好的数组，所以需要判断 index 的位置是否小于 left，小于的话，需要更新 index 位置。

代码

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left = 0
        right = len(nums) - 1
        index = 0
        while index <= right:
            if index < left:
                index += 1
            elif nums[index] == 0:
                nums[index], nums[left] = nums[left], nums[index]
                left += 1
            elif nums[index] == 2:
                nums[index], nums[right] = nums[right], nums[index]
                right -= 1
            else:
                index += 1