颜色分类

Leetcode Link: 75. 颜色分类 - 力扣（LeetCode） (leetcode-cn.com)

题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

解法一

思路：直接使用任意一种排序算法都可以完成，这里略

解法二

思路：其实是三指针法，典型的荷兰国旗问题，是快速排序的一种进阶。 相当于将一个数组分成了 3 个区域，左侧 [0, left) 为全是 0 的区域，中间 [left, mid) 为全是 1 的区域，右侧 (right,end] 为全是 2 的区域

可以看出，是左侧区域“推着”中间区域再往前走

mid一直往前走，遇到没看过的原地不动。分解成以下步骤：

1. mid 遇到了 0，就和 left 交换，此时 left 肯定是 1（不含边界），因此 mid++，同时left++（总把left++忘了）
2. mid 遇到了 1，就是属于本区域的，直接 mid++
3. mid 遇到了 2，需要换到右侧区域，因此和 right 交换，此时换过来的值没看过，mid 不变，只更新 right--

题解：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 都不含边界
        left = mid = 0
        right = len(nums) -1
 
        while(mid-1 != right): # 注意这里的判定，并不是 mid!=right
            if nums[mid] == 0:
	            # 换到左侧，两个边界++
                nums[mid], nums[left] = nums[left], nums[mid]
                mid += 1
                left += 1
            elif nums[mid] == 1:
	            # 就属于本区域，就mid++
                mid += 1
            elif nums[mid] == 2:
	            # 换到右侧边界，换过来的没见过
	            # mid 不变，right--
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1

启发和联系