文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《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 p2nums[i] 0与nums[p0]交换p0i因为交换过来的只可能是 1 或当前元素自身不需要二次检查。nums[i] 1属于中间区域直接i。nums[i] 2与nums[p2]交换p2--注意此时i不能自增因为从p2换过来的元素尚未检查可能是 0 或 2下一轮循环需要继续判断当前的nums[i]。2、解题代码classSolution{public:voidsortColors(vectorintnums){// p00的最右边界下一个0应该放置的位置即 nums[0...p0-1] 全为0// p22的最左边界下一个2应该放置的位置即 nums[p21...n-1] 全为2intp00,p2nums.size()-1;// i当前遍历指针维护 nums[p0...i-1] 全为 1inti0;// 当 i p2 时说明未处理区间为空排序完成while(ip2){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 k3k3。需要先统计各元素出现次数再回填数组代码更直观但需要额外空间。共同点两者都能在线性时间内完成排序。区别在于三指针法通过交换实现原地排序而计数排序依赖计数数组回填。三指针法的设计思想核心思想把「排序」问题转化为「区间划分」问题——通过指针维护边界让每个元素在遍历过程中直接落入正确区间无需回溯。与本题的联系颜色分类问题天然具有「三值」特性——每个元素只能是 0、1、2 之一。因此可以用三个指针分别维护 0 区右边界、1 区右边界、2 区左边界一次遍历即可完成全部归位。注意事项当nums[i] 2时与nums[p2]交换后i不能自增因为换过来的元素可能是 0 或 2需要下一轮继续判断而当nums[i] 0时与nums[p0]交换后i可以直接自增因为换过来的只可能是 1 或当前元素自身。使用要点指针初始化p0 0p2 nums.size() - 1i 0循环条件为i p2。交换逻辑nums[i] 0时与nums[p0]交换并p0、inums[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 个最大元素快速选择 分区思想