【技巧】LC 75.颜色分类

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

75.颜色分类

2、题目描述

二、个人思路整理

1、思路分析

核心思路：三指针法/荷兰国旗算法
利用三个指针将数组划分为 4 个区间：

• [0, p0)：全为 0（红色）
• [p0, i)：全为 1（白色）
• [i, p2]：未处理区域
• (p2, n - 1]：全为 2（蓝色）

指针移动逻辑：
维护当前指针i（从 0 开始）以及边界指针p0 = 0和p2 = nums.size() - 1，循环条件为i <= p2：

1. nums[i] == 0：
   • 与nums[p0]交换；
   • p0++，i++（因为交换过来的只可能是 1 或当前元素自身，不需要二次检查）。
2. nums[i] == 1：
   • 属于中间区域，直接i++。
3. nums[i] == 2：
   • 与nums[p2]交换；
   • p2--；
   • 注意：此时i不能自增，因为从p2换过来的元素尚未检查（可能是 0 或 2），下一轮循环需要继续判断当前的nums[i]。

2、解题代码

classSolution{public:voidsortColors(vector<int>&nums){// p0：0的最右边界（下一个0应该放置的位置，即 nums[0...p0-1] 全为0）// p2：2的最左边界（下一个2应该放置的位置，即 nums[p2+1...n-1] 全为2）intp0=0,p2=nums.size()-1;// i：当前遍历指针，维护 nums[p0...i-1] 全为 1inti=0;// 当 i > p2 时，说明未处理区间为空，排序完成while(i<=p2){if(nums[i]==0){// 遇到 0：与 p0 处的元素交换，放入左侧 0 区间swap(nums[i],nums[p0]);p0++;// 换过来的元素只可能是 1（当 p0 < i 时）或者就是当前的 0 （当 p0 == i 时）// 因此该位置已确认符合顺序，i 直接右移i++;}elseif(nums[i]==2){// 遇到2：与 p2 处的元素交换，放入右侧 2 区间swap(nums[i],nums[p2]);p2--;// 注意：此时换到 nums[i] 的元素尚未经过检验（可能是 0、1或2）// 因此 i 不能自增，下一轮循环需继续检查当前的 nums[i]}else{// 遇到 1：本身就处于中间区间，直接跳过i++;}}}};

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，每个元素最多被交换/访问两次。
• 空间复杂度：O ( 1 ) O(1)O(1)，常数个变量空间占用。

三、知识风暴

三指针法（荷兰国旗算法）是本题的核心算法思想。它通过维护三个指针，将数组划分为 4 个区间，在一次遍历中完成所有元素的归位，从而以O ( n ) O(n)O(n)的时间复杂度高效求解。

算法核心思想：

• 区间划分：利用p0、i、p2三个指针，将数组划分为「全 0 区」「全 1 区」「未处理区」「全 2 区」四个区间，每个元素只需被访问一次即可确定最终位置。
• 指针移动：p0指向下一个 0 应放置的位置，p2指向下一个 2 应放置的位置，i为当前遍历指针。当i越过p2时，未处理区间为空，排序完成。
• 与排序算法的区别：普通排序（如快速排序、归并排序）需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的比较交换；而本题元素取值只有 0、1、2 三种，三指针法利用这一特性，将复杂度降到线性O ( n ) O(n)O(n)，且空间复杂度为O ( 1 ) O(1)O(1)。

常见对比：三指针法 vs 计数排序

• 三指针法：时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 1 ) O(1)O(1)。只需一次遍历即可完成排序，且不需要额外数组，适合对数组进行原地排序的场景。
• 计数排序：时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( k ) O(k)O(k)（k kk为取值种类数，本题k = 3 k=3k=3）。需要先统计各元素出现次数，再回填数组，代码更直观但需要额外空间。
• 共同点：两者都能在线性时间内完成排序。区别在于三指针法通过交换实现原地排序，而计数排序依赖计数数组回填。

三指针法的设计思想：

• 核心思想：把「排序」问题转化为「区间划分」问题——通过指针维护边界，让每个元素在遍历过程中直接落入正确区间，无需回溯。
• 与本题的联系：颜色分类问题天然具有「三值」特性——每个元素只能是 0、1、2 之一。因此可以用三个指针分别维护 0 区右边界、1 区右边界、2 区左边界，一次遍历即可完成全部归位。
• 注意事项：当nums[i] == 2时，与nums[p2]交换后i不能自增，因为换过来的元素可能是 0 或 2，需要下一轮继续判断；而当nums[i] == 0时，与nums[p0]交换后i可以直接自增，因为换过来的只可能是 1 或当前元素自身。

使用要点：

• 指针初始化：p0 = 0，p2 = nums.size() - 1，i = 0，循环条件为i <= p2。
• 交换逻辑：nums[i] == 0时与nums[p0]交换并p0++、i++；nums[i] == 2时与nums[p2]交换并p2--（i不自增）；nums[i] == 1时直接i++。
• 终止条件：当i > p2时，未处理区间为空，此时[0, p0)全为 0、[p0, i)全为 1、(p2, n-1]全为 2，排序完成。
• 结果返回：排序在原数组上原地完成，无需返回值。

算法变体与扩展：

• 移动零（LeetCode 283）：本质是「双指针」的简化版，只区分 0 和非 0 两类元素，用快慢指针将非零元素前移、零元素后移。
• 奇偶排序：将数组按奇偶性划分，与本题「按值划分」思路一致，可用双指针分别维护奇偶边界。
• 三路快排（Quick Sort 3-way）：快速排序在处理大量重复元素时的优化版本，正是借鉴了荷兰国旗算法的三指针思想，将数组划分为「小于」「等于」「大于」三个区间。

相关 LeetCode 例题：

• 283. 移动零（双指针 + 区间划分）
• 905. 按奇偶排序数组（双指针 + 奇偶划分）
• 912. 排序数组（三路快排优化）
• 215. 数组中的第 K 个最大元素（快速选择 + 分区思想）