LC75. 颜色分类

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 示例 1： 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 示例 2： 输入：nums = [2,0,1] 输出：[0,1,2] 提示： n == nums.length 1 <= n <= 300 nums[i] 为 0、1 或 2

题目解析

题目在说什么

这道题其实是在说：给你一堆数字，里面只有 0、1、2 三种数，分别代表红色、白色、蓝色。你要把它们排好序，让所有 0 在前面，所有 1 在中间，所有 2 在最后面。而且不能直接用排序函数，要“原地”改数组，也就是不能新建一个数组来存结果。

比如例子： 输入 [2,0,2,1,1,0] 输出应该是 [0,0,1,1,2,2]

思路是怎么来的

想象你面前有一排球，红的、白的、蓝的混在一起。你要把它们按红、白、蓝的顺序排好。 你手里有三个“指针”或者叫“标记”：

• 一个指针指向“红色应该放的位置”（我们叫它 left）
• 一个指针指向“蓝色应该放的位置”（叫它 right）
• 还有一个指针在中间来回走，检查每个球是什么颜色（叫它 i）

一开始，left 在最左边（位置 0），right 在最右边（位置 n-1），i 也从最左边开始。

规则很简单：

• 如果 i 指到的球是红色（0），就把它换到 left 的位置，然后 left 向右移一格，i 也向右移一格。
• 如果 i 指到的球是蓝色（2），就把它换到 right 的位置，然后 right 向左移一格。注意，这时候 i 不急着动，因为换过来的球可能是红色或白色，需要再检查一次。
• 如果 i 指到的球是白色（1），就什么都不做，直接让 i 向右移一格。

这样一步步走，红色都跑到左边，蓝色都跑到右边，白色自然就留在中间了。

代码逐步拆解

我们来看一个常见的写法（Python 风格，但逻辑通用）：

def sortColors(nums):
    left = 0          # 红色应该放的位置
    right = len(nums) - 1  # 蓝色应该放的位置
    i = 0             # 当前检查的位置

    while i <= right:
        if nums[i] == 0:
            # 把红色换到左边
            nums[left], nums[i] = nums[i], nums[left]
            left += 1
            i += 1
        elif nums[i] == 2:
            # 把蓝色换到右边
            nums[right], nums[i] = nums[i], nums[right]
            right -= 1
            # 注意：这里 i 不加 1，因为换过来的可能是 0 或 1，需要再检查
        else:
            # 白色，不动，继续往前走
            i += 1

逐步拆解：

1. 初始化 left = 0：红色应该放在最左边，目前左边第一个位置是 0。 right = len(nums)-1：蓝色应该放在最右边，目前右边最后一个位置是数组长度减 1。 i = 0：从第一个位置开始检查。

2. 循环条件 while i <= right 为什么是 i <= right？因为 right 右边的位置都已经放好了蓝色，我们不需要再检查它们。当 i 超过 right 时，说明所有位置都检查完了。

3. 遇到 0（红色）

• 把 nums[i] 和 nums[left] 交换。
• 为什么交换？因为 left 位置是“下一个红色应该放的地方”，把红色放过去。
• 交换后，left 向右移一格，表示红色区域扩大了一个位置。
• i 也向右移一格，因为换过来的 nums[left] 原本是什么？它原本可能是 0 或 1（因为 2 已经被换到右边了），但我们已经处理过它了，所以可以继续往前走。

4. 遇到 2（蓝色）

• 把 nums[i] 和 nums[right] 交换。
• 为什么交换？因为 right 位置是“下一个蓝色应该放的地方”，把蓝色放过去。
• 交换后，right 向左移一格，表示蓝色区域扩大了一个位置。
• 但是 i 不移动！因为换过来的 nums[right] 原本是什么？它可能是 0、1 或 2。如果是 0 或 1，我们需要再检查一次，所以 i 不动，下一轮循环继续判断这个新来的数。

5. 遇到 1（白色）

• 什么都不做，直接 i += 1，继续看下一个位置。因为白色就应该在中间，不需要交换。

举个例子跑一遍：