7.1 分治-快排专题：LeetCode 75. 颜色分类

1. 题目链接

LeetCode 75. 颜色分类

2. 题目描述

给定一个包含红色（0）、白色（1）和蓝色（2）的数组 nums，要求原地对数组进行排序，使得相同颜色的元素相邻，且按红、白、蓝顺序排列。
要求：

• 仅使用常数空间。
• 仅遍历数组一次。

示例：

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

3. 示例分析

1. 常规案例：
   • 输入：[2,0,2,1,1,0]
     • 通过交换将 0 移动到左侧，2 移动到右侧，中间保留 1。
     • 最终结果：[0,0,1,1,2,2]。
2. 边界案例：
   • 输入全为 0：[0,0,0] → 无需操作，直接返回。
   • 输入全为 2：[2,2,2] → 所有元素交换到右侧。
   • 输入全为 1：[1,1,1] → 无需操作。

4. 算法思路

核心思想：三指针法

1. 指针定义：
   • left：指向已处理 0 的右边界（初始为 -1）。
   • right：指向已处理 2 的左边界（初始为 n）。
   • i：遍历指针，从 0 开始。
2. 遍历规则：
   • nums[i] == 0：
     • 交换 nums[++left] 和 nums[i]，i++。
     • 将 0 移动到 left 右侧，扩展 0 的区域。
   • nums[i] == 1：
     • i++。
     • 1 保留在中间区域，无需处理。
   • nums[i] == 2：
     • 交换 nums[--right] 和 nums[i]。
     • 将 2 移动到 right 左侧，扩展 2 的区域。
     • 不移动 i：交换后的 nums[i] 可能是 0 或 1，需再次检查。
3. 终止条件：
   • 当 i >= right 时，所有元素已处理完毕。

5. 边界条件与注意事项

1. 全 0/1/2 数组：
   • 全 0 或 1：遍历后指针无需移动，直接返回。
   • 全 2：i 不移动，通过交换将所有元素移动到右侧。
2. 单元素数组：
   • 无需操作，直接返回。
3. 元素交换顺序：
   • 交换 2 时，i 不自增，确保新元素被检查。
4. 时间复杂度：
   • 每个元素最多被交换两次，时间复杂度为 O(n)。

6. 代码实现

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = n, i = 0;
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums[++left], nums[i++]); // 交换0到左区，i前进
            } else if (nums[i] == 1) {
                i++; // 保留中间区
            } else {
                swap(nums[--right], nums[i]); // 交换2到右区，i不前进
            }
        }
    }
};

关键步骤解析

1. 初始化指针：

   int left = -1, right = n, i = 0;
   

   • left 初始指向 0 区的左边界（无元素），right 指向 2 区的右边界。

2. 处理 0 的逻辑：

   swap(nums[++left], nums[i++]);
   

   • left 向右扩展，将 0 交换到 0 区末尾，i 前进。

3. 处理 2 的逻辑：

   swap(nums[--right], nums[i]);
   

   • right 向左扩展，将 2 交换到 2 区头部，i 不前进。

与其他解法的对比

总结

三指针法通过一次遍历实现原地排序，是解决荷兰国旗问题的经典方案。其核心在于 分区处理 和 指针动态调整，以线性时间高效完成排序。

优化点：

• 合并部分条件判断，减少代码行数。
• 预判全 1 情况，提前终止遍历。

适用场景：

• 需要严格满足“一次遍历”和“常数空间”要求的场景。
• 大规模数据排序（n ≤ 1e5）。

关键点：

• 理解 i 与 right 的协作逻辑。
• 处理 0 和 2 时的指针移动差异。