75. 颜色分类

题目描述

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

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

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

示例 1：

text

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

示例 2：

text

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

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

思路拆解

这是一个经典的 荷兰国旗问题 (Dutch National Flag Problem)。

我们需要将数组分为三个区域：

红色区域 (0)：在数组的前部。
白色区域 (1)：在数组的中部。
蓝色区域 (2)：在数组的后部。

我们可以使用 三指针 (Three Pointers) 的方法来实现一次遍历排序：

定义三个指针：
- p0：指向红色区域（0）的右边界（下一个存放 0 的位置），初始为 0。
- p2：指向蓝色区域（2）的左边界（下一个存放 2 的位置），初始为 n - 1。
- curr：当前遍历的指针，初始为 0。
遍历数组（当 curr <= p2 时）：
- 如果 nums[curr] === 0：
  - 当前元素是红色，应该放到前面。
  - 交换 nums[curr] 和 nums[p0]。
  - p0 向右移动（p0++），因为该位置已经填好了 0。
  - curr 向右移动（curr++），因为交换回来的元素肯定是 1（或者初始时 curr == p0），不需要再处理。
- 如果 nums[curr] === 1：
  - 当前元素是白色，位置正确（在中间）。
  - 直接移动 curr（curr++）。
- 如果 nums[curr] === 2：
  - 当前元素是蓝色，应该放到后面。
  - 交换 nums[curr] 和 nums[p2]。
  - p2 向左移动（p2--），因为该位置已经填好了 2。
  - 注意：此时 curr 不移动。因为从 p2 交换过来的元素可能是 0 或 1，我们需要在下一次循环中继续判断这个位置的新元素。

代码实现

javascript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let p0 = 0;             // 指向 0 的放置位置
    let curr = 0;           // 当前遍历指针
    let p2 = nums.length - 1; // 指向 2 的放置位置

    while (curr <= p2) {
        if (nums[curr] === 0) {
            // 遇到 0，交换到 p0 位置
            [nums[curr], nums[p0]] = [nums[p0], nums[curr]];
            p0++;
            curr++;
        } else if (nums[curr] === 1) {
            // 遇到 1，跳过
            curr++;
        } else {
            // 遇到 2，交换到 p2 位置
            // 注意：curr 不自增，因为交换过来的元素还需要判断
            [nums[curr], nums[p2]] = [nums[p2], nums[curr]];
            p2--;
        }
    }
};

运行演示

假设 nums = [2, 0, 2, 1, 1, 0]

初始状态：p0 = 0, curr = 0, p2 = 5。
curr = 0, nums[0] = 2：
- 交换 nums[0] 和 nums[5] -> [0, 0, 2, 1, 1, 2]
- p2-- -> p2 = 4
- curr 不变。
curr = 0, nums[0] = 0：
- 交换 nums[0] 和 nums[0] -> [0, 0, 2, 1, 1, 2] (无变化)
- p0++ -> p0 = 1
- curr++ -> curr = 1
curr = 1, nums[1] = 0：
- 交换 nums[1] 和 nums[1]
- p0++ -> p0 = 2
- curr++ -> curr = 2
curr = 2, nums[2] = 2：
- 交换 nums[2] 和 nums[4] (1) -> [0, 0, 1, 1, 2, 2]
- p2-- -> p2 = 3
- curr 不变。
curr = 2, nums[2] = 1：
- curr++ -> curr = 3
curr = 3, nums[3] = 1：
- curr++ -> curr = 4
curr = 4, p2 = 3，循环结束。

结果：[0, 0, 1, 1, 2, 2]，排序完成。

复杂度分析

时间复杂度：$O(n)$，其中 n 是数组的长度。我们需要遍历数组一次。
空间复杂度：$O(1)$，只需要常数个额外空间用于存储指针。

75. 颜色分类 ​

题目描述 ​

思路拆解 ​

代码实现 ​