LeetCode 第 75 题：颜色分类（Sort Colors）

题目描述

给定一个包含红色（0）、白色（1）和蓝色（2）的数组，你需要原地（in-place）对它们进行排序，使得相同颜色的元素相邻，且按照红色、白色、蓝色的顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

注意：不能使用代码库中的排序函数来解决这道题。

示例：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

解题思路

这道题本质上是将数组中的 0、1、2 进行排序，但要求原地排序且时间复杂度为 O(n)。我们可以使用 三指针法（或称荷兰国旗问题解法）来高效解决。

关键思路

维护三个指针：

• left：指向下一个 0 应该放置的位置（即已排序的 0 的末尾的下一个位置）。
• right：指向下一个 2 应该放置的位置（即已排序的 2 的开头的前一个位置）。
• curr：当前遍历的指针。

通过交换元素，将 0 移到左边，2 移到右边，1 自然留在中间。

详细步骤

1. 初始化指针：

   • left = 0：从数组开头开始，用于放置 0。
   • right = len(nums) - 1：从数组末尾开始，用于放置 2。
   • curr = 0：从开头开始遍历。

2. 遍历数组：

   • 当 curr <= right 时，继续遍历（因为 right 之后的元素已经是 2，无需再处理）。

3. 处理当前元素 nums[curr]：

   • 如果 nums[curr] == 0：
     • 将 nums[curr] 与 nums[left] 交换，将 0 移到左边。
     • 因为 left 位置可能是 1 或 0，交换后 nums[curr] 可能是 1 或 0，但此时 left 位置的元素已处理，所以 left 和 curr 都向右移动一位。
   • 如果 nums[curr] == 2：
     • 将 nums[curr] 与 nums[right] 交换，将 2 移到右边。
     • 交换后 nums[curr] 可能是 0、1 或 2，需要再次检查 curr 位置，所以 curr 不移动，但 right 向左移动一位（因为右边已放好一个 2）。
   • 如果 nums[curr] == 1：
     • 1 应该留在中间，直接移动 curr 指针向右一位。

4. 终止条件：

   • 当 curr > right 时，说明所有元素已处理完毕。

举例说明

以 nums = [2,0,2,1,1,0] 为例：

• 初始：left=0, curr=0, right=5，数组为 [2,0,2,1,1,0]。
• curr=0：nums[0]=2，与 right=5 交换，数组变为 [0,0,2,1,1,2]，right=4，curr 仍为 0。
• curr=0：nums[0]=0，与 left=0 交换（原地交换），数组不变，left=1，curr=1。
• curr=1：nums[1]=0，与 left=1 交换，数组不变，left=2，curr=2。
• curr=2：nums[2]=2，与 right=4 交换，数组变为 [0,0,1,1,2,2]，right=3，curr 仍为 2。
• curr=2：nums[2]=1，直接移动 curr=3。
• curr=3：nums[3]=1，直接移动 curr=4。
• 此时 curr=4 > right=3，结束。

最终数组为 [0,0,1,1,2,2]。

代码实现（Python）

def sortColors(nums):
    left, curr, right = 0, 0, len(nums) - 1
    while curr <= right:
        if nums[curr] == 0:
            nums[curr], nums[left] = nums[left], nums[curr]
            left += 1
            curr += 1
        elif nums[curr] == 2:
            nums[curr], nums[right] = nums[right], nums[curr]
            right -= 1
        else:  # nums[curr] == 1
            curr += 1

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。
• 空间复杂度：O(1)，仅使用常数级额外空间。

这种方法高效且直观，确保在一次遍历内完成排序，符合题目要求。