颜色分类题解：荷兰国旗问题的双指针原地排序与边界细节

“颜色分类”这个题在算法题库里排第75位更广为人知的叫法是“荷兰国旗问题”。我第一次刷到它的时候觉得不过是给数组排个序能有什么花头但真正在纸上写的时候才发现题目虽然短约束只有两条——“原地”和“不准调用排序函数”却恰好把常规排序思路、计数思路、双指针思路全考了一遍。后来我自己也拿这道题考过几位候选人几乎每次都能从实现细节里看出对方对数组分区的理解深度。这篇就把这题的三种解法、双指针实现的完整推导、以及我实际写代码时踩过的坑一次性讲清楚。不管你是刚开始刷题找工作的学生还是想补一补数组双指针基本功的开发者这题都值得认真吃透。1. 这道题到底在考什么1.1 题目描述与核心约束先原原本本把题目复述一遍。给定一个包含红色、白色和蓝色一共 n 个元素的数组要求原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。实际编码时用整数 0、1、2 分别代表红、白、蓝。看起来这就是个排序题但要注意两个硬性约束第一个是“原地”意味着不能new一个额外的数组再把结果拷回去第二个是“不调用排序函数”注意这里说的是库函数比如各种语言里现成的sort方法都算违规。也就是说你得手动完成这个排序过程。我见过不少第一次做这题的读者第一反应是“用Arrays.sort不就行了”或者“冒泡排序走一趟”确实能得出正确结果但完全没用到题目的特殊性。这里最容易被忽略的信息是数组里只有三种取值。这个条件会直接影响最优解的设计方向。如果是一般排序题元素之间可能存在任意大小关系我们只能用通用的比较排序或非比较排序但这里元素种类被锁死成三类排序问题就退化成了“分区问题”。1.2 从“排序”到“分区”换个视角理解问题当数组里只有 0、1、2 三种数字时最终结果一定长这样前面一片是 0中间一片是 1后面一片是 2。所以排序的本质是把整个数组切割成三个连续区间。这个视角转换非常重要因为一旦你意识到这里做的是“三区间分割”而不是“任意序列排序”后面所有解法就顺理成章了。“分区”和“排序”的区别在哪里普通排序关心的是元素之间的相对顺序比如 5 和 3 谁排前面分区关心的是“这类元素放哪一段”至于区间内部的顺序根本不重要。拿一个生活化的例子来说整理衣柜时把T恤放一格、衬衫放一格、裤子放一格这就是分区而给每件衣服按尺码从小到大排那才是排序。颜色分类这道题只让你做前者如果把它当后者做等于杀鸡用了牛刀。理解了这个视角再回看题目很快就发现普通排序算法在这里不仅慢而且绕远路。我们真正要设计的是一个“扫描过程中随时把元素丢进正确分区”的算法。1.3 面试官想看到的三个能力以我个人的观察面试官出这道题并不指望你背答案而是想通过代码看出三种能力。第一能否识别问题本质。看到 0、1、2 三种值能不能第一时间想到这是“三区间分区”问题而不是泛泛地调用排序函数。第二能否驾驭双指针控制边界。双指针不是简单的一左一右对碰而是三个指针相互配合各自维护一个区间的边界。代码写出来可能只有十几行但每一行边界的含义必须非常清晰。第三面对边界条件的敏感性。数组为空、数组只有一种颜色、当前指针已经越过右指针这些场景能不能正确处理。很多人算法大方向对细节一跑就挂往往就是边界条件没想明白。读到这里你应该明白这道题表面是排序实际是考察“如何用指针维护区间不变量”。接下来把三种常见解法逐一拆开看你就会发现它们的复杂度差异有多大。2. 三种解法从上到下逐步逼近最优解2.1 解法一先统计再重写整个数组最容易想到的思路是先扫描一遍数组数一数 0、1、2 分别有多少个然后按照数量把数组重新填一遍。public void sortColors(int[] nums) { int count0 0, count1 0, count2 0; for (int num : nums) { if (num 0) count0; else if (num 1) count1; else count2; } int index 0; while (count0-- 0) nums[index] 0; while (count1-- 0) nums[index] 1; while (count2-- 0) nums[index] 2; }这个解法的时间复杂度是 O(n)额外空间是 O(1)。严格来说它已经比调用比较排序的 O(n log n) 好很多。但它有个小瑕疵总共要遍历数组两遍第一遍数数第二遍回填。有一些刁钻的面试官会追问“能不能只遍历一遍”这时候这种解法就不够看。我自己在实际教学中常把这种方案称为“能用但不够优雅”因为它的思路与数组只有三类元素这个事实契合度很高简单、直观、几乎不可能写错。如果你在笔试环节时间紧张这绝对是一个可以保底的方案。但如果你要展示自己的工程思维就继续往下看。2.2 解法二通用排序算法为什么在这题里吃亏还有人会想直接用快速排序或者内置排序函数代码更短。确实哪种语言里都能一行调库搞定。但这题的数组里只有三个取值你用比较排序等于在让计算机做很多无意义的比较。举个例子数组[2, 0, 1]长度只有 3快速排序至少要两三次分区比较而基于分区的双指针方案眼睛扫一遍就分好了。更关键的是很多面试场景下考官会明令禁止调用排序函数目的就是逼你结合题目特性去设计算法。所以在面试中哪怕你写出了正确的调用排序解法也拿不到这题的高分。从实际复杂度来看比较排序普遍是 O(n log n) 或 O(n^2)对一个确定只有三种取值的数组来说无论是快速排序还是插入排序都是大材小用。这就像一个整理书架的人明明只需要把书按“精装、平装、线装”分成三堆却非要按作者姓名做全量字典排序一样多余的精力全花在了不重要的事情上。2.3 解法三三指针一趟扫描最优解登场最优解法利用三个指针在从头到尾一次遍历的过程中把数组切成三段边界逐渐扩大、中间待处理区域逐渐缩小的形态。这也是荷兰国旗问题的标准解法专门解决“把三类元素按顺序分区”的需求。public void sortColors(int[] nums) { int p0 0, curr 0, p2 nums.length - 1; while (curr p2) { if (nums[curr] 0) { swap(nums, p0, curr); p0; curr; } else if (nums[curr] 1) { curr; } else { swap(nums, curr, p2); p2--; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }这段代码就是经典的荷兰国旗双指针解法。它与统计重排的核心差异在于两个指针从左边界和右边界同时向中间收缩待处理区域第三个指针则负责逐一检查这些待处理元素。整个过程只遍历一遍时间复杂度 O(n)空间复杂度 O(1)。如果把三种解法放在一起对比差异非常清楚解法时间复杂度空间复杂度遍历次数是否推荐调用通用排序O(n log n)O(1) 或 O(log n)多次不推荐统计重排O(n)O(1)2 次可保底三指针分区O(n)O(1)1 次推荐光看代码可能觉得双指针版也没多复杂但实际上“为什么遇到 0 时两个指针都前进遇到 2 时只有右指针收缩”这段逻辑是整个算法最微妙的点。下一节我就把它的原理一层层剥开讲明白。3. 双指针解法完整拆解原理、实现与手动模拟3.1 循环不变量三个指针各管一段区域这段代码能写对的关键在于你心里时刻清楚三个指针指代的是什么。我给三个指针分别赋予明确的职责。p0下一个 0 应该放的位置也就是“全 0 区域”的右边界。curr当前正在检查的元素下标它把已扫描区域和未扫描区域分开。p2下一个 2 应该放的位置也就是“全 2 区域”的左边界。在整个遍历过程中数组始终维持这条“不变式”[0, p0)范围内的元素全部是 0[p0, curr)范围内的元素全部是 1(p2, n-1]范围内的元素全部是 2而[curr, p2]是还没处理完的未知区域。循环每执行一步未知区域就少一个元素直到curr越过p2未知区域清空。这个“循环不变量”概念听上去很工程化其实类比一下立刻明白。想象你在整理一排任意混放的红白蓝球左手边筐里装红球右手边筐里装蓝球白球留在中间。你站在白球区域的起点从左往右检查每一颗球如果是红球就跟左手边的上一个位置交换然后你和左边界都前进一步如果是白球直接跳过如果是蓝球就跟右手边的上一个位置交换但你要站在原地多看一眼——因为换过来的是什么颜色你还没确认。等你的位置和右手边界交叉时整排球就分好了。3.2 遇到 0 时为什么两个指针都要前进当nums[curr] 0时执行交换nums[p0]和nums[curr]然后p0、curr。这里初学者最爱问的一个问题是curr之后不会漏掉从p0换过来的元素吗答案是不会因为可以从循环不变量推出p0位置的元素只可能是 0 或 1。如果p0 curr那么[p0, curr)这一整段都是 1所以换过来的必定是 1如果p0 curr那交换等于没交换当前元素本来就是 0换完之后当然也还是 0。换句话说从左边换过来的元素一定已经被处理过不需要再检查所以两个指针可以安心地一起前进。这一步能想通双指针的用法就入门了一半。它不像普通交换那样只关心“把A放到B位置”还要时刻关心“B位置原来的值是否安全”。3.3 遇到 2 时为什么只能动右指针不能动当前位置当nums[curr] 2时执行交换nums[curr]和nums[p2]然后只执行p2--curr保持不变。这个不对称之处是所有写错这段代码的人最容易栽的跟头。原因很简单p2从右侧拿来交换的元素可能属于三类中的任意一类。因为右侧(p2, n-1]虽然已经是全 2但p2本身是一个未处理边界上的元素它可能是 0、可能是 1、也可能是 2。如果这里也让curr就会跳过对换过来元素的判断可能把 0 或 1 错误地带进 2 区域里。比如[0, 2, 1]第一次交换把 1 换回当前位置如果不加检查直接推进1 就会被留在 2 的区域里结果变成错误的[0, 2, 1]。所以处理 2 的正确姿势是先交换再把右侧边界收缩一位然后重新回到while循环的开头把换回来的元素重新走一遍分类逻辑。3.4 遇到 1 时直接推进nums[curr] 1的情况最简单因为 1 本来就应该落在中间白色区域。此时[p0, curr)会扩张一位当前的 1 自动成为已处理的一部分只需要curr。代码里甚至可以单独把这种分支放在中间逻辑顺序是“0 优先放左2 优先放右1 留在原地”。这里有一点值得提醒如果你把if / else if / else的顺序调整成“先判断 1再判断 0再判断 2”结果也是对的因为三种分支互斥。但最直观的阅读顺序依然是 0、1、2这样和最终目标区间一一对应方便复查。3.5 手动跑一遍完整示例理论说得再多不如拿一个具体数组逐步走一遍。就用题目描述里的经典例子[2, 0, 2, 1, 1, 0]。初始化时p0 0curr 0p2 5。第一步nums[curr]是 2交换nums[0]和nums[5]数组变成[0, 0, 2, 1, 1, 2]p2减为 4curr依然是 0。换回来的 0 还没检查继续下一轮。第二步nums[0]是 0与nums[0]自身交换数组不变p0变为 1curr变为 1。注意这一步交换的是同一个位置但逻辑上依然把 0 归位了。第三步nums[1]是 0交换nums[1]和nums[1]数组仍为[0, 0, 2, 1, 1, 2]p0变为 2curr变为 2。第四步nums[2]是 2交换nums[2]和nums[4]数组变成[0, 0, 1, 1, 2, 2]p2减为 3curr保持 2。第五步nums[2]是 1curr变为 3。第六步nums[3]是 1curr变为 4。此时curr 4大于p2 3循环退出最终数组是[0, 0, 1, 1, 2, 2]。这个手动过程可以清楚看到三种分区的边界如何一点点收窄、待处理区域如何一步步缩小。建议你在纸上多跑几个例子比如[1, 2, 0]、[2, 1, 0]、[0, 0, 1, 1]跑熟了之后代码就不容易写错。3.6 复杂度与代码细节时间上每个元素最多被curr检查两次一次是它出现在当前位置时另一次是被右边交换回来后再次检查。但每次循环都会缩小未知区域或者推进curr所以整体是严格的 O(n)。空间上只有p0、curr、p2三个整数变量加上交换的临时变量一共 O(1)。除了 Java 版本Python 的写法也值得记住很多读者面试时用的是 Pythondef sort_colors(nums): p0, curr, p2 0, 0, len(nums) - 1 while curr p2: if nums[curr] 0: nums[p0], nums[curr] nums[curr], nums[p0] p0 1 curr 1 elif nums[curr] 1: curr 1 else: nums[curr], nums[p2] nums[p2], nums[curr] p2 - 1Python 的多元赋值交换虽然写起来简洁有一个细节要注意交换的赋值顺序在nums列表上并不会影响结果因为右侧先求值再统一赋值。但如果你在循环条件、下标计算上依赖旧值务必多留个心眼否则容易出现“交换后下标错位”的诡异表现。4. 实操中容易踩的坑高频 Bug 与排查指南4.1 高频 Bug 一遇到 2 之后忘记让 curr 原地等待这是出现频率最高、也最隐蔽的问题。很多人交换完 2 之后顺手写一个curr自以为逻辑完整跑测试用例时恰好在某些数据上出错。我见过一个典型的错误现场输入[1, 2, 0]正确结果是[0, 1, 2]。如果在处理 2 时也让curr过程会变成curr0看到 1推进curr1看到 2和p22交换数组变为[1, 0, 2]然后curr变成 2p2--变成 1循环条件curr p2变成2 1为假直接退出最终数组是[1, 0, 2]显然错误。原因就是换回来的 0 没有进入判断分支。所以排查这种问题时不要先查交换逻辑先看curr在处理 2 的分支有没有自增。正确写法里这种不对称是刻意设计的不是笔误。4.2 高频 Bug 二循环边界写成 curr p2循环条件到底用curr p2还是curr p2很多人会纠结。我的建议是使用curr p2因为当curr p2时这个位置的元素还没有被检查过它需要再走一轮分类。来一个反例验证输入[2, 0, 1]如果循环条件写成curr p2初始化curr0、p22。nums[0]是 2与nums[2]交换得到[1, 0, 2]p2减为 1curr0 p21进入循环nums[0]是 1curr变为 1。此时curr1 p21不成立循环退出结果[1, 0, 2]0 和 1 的顺序错了。原因就是curr p2时该检查的元素没检查就提前收工。反观[2, 0, 1]用curr p2交换后p21, curr0进入循环nums[0]是 1curr1现在curr1 p21继续检查nums[1]发现是 0与p00交换得到[0, 1, 2]p01, curr2退出循环。最后结果正确。别看只差一个等号实际跑起来结果差出十万八千里。4.3 高频 Bug 三把 0 和 1 的处理顺序弄混虽然 0、1、2 三个分支互斥理论上顺序不影响正确性但如果你把if (nums[curr] 1)放在if (nums[curr] 0)前面代码可读性下降不说很容易在后面加其他分支时出现覆盖问题。比如有人写出if (nums[curr] 0) { ... } if (nums[curr] 1) { ... } else { ... }第二句用了一个独立的if而不是else if那么当第一个分支处理完 0 后nums[curr]已经被换成了 1第二句的if (nums[curr] 1)可能会再次执行导致边界错乱。这类问题用if / else if / else严格串起来就能规避千万别图省事把else丢掉。4.4 测试用例设计建议每次写完代码别急着提交先把边界用例跑一遍。我常用的用例集合是用例目的空数组验证循环不会越界[0]、[1]、[2]验证单一元素场景[0, 0, 0]验证全 0 数组不需要交换[1, 1, 1]验证全 1 数组只走 curr 分支[2, 2, 2]验证全 2 数组右边界持续收缩[2, 0, 1]验证边界上的交换[1, 2, 0]验证处理 2 后换回 0 的场景[2, 1, 0]验证三种值都出现在交换路径上随机长数组用暴力统计法做对照验证你可以把题目自带的测试用例全跑一遍再用随机数组做一次“正确性对拍”基本能覆盖所有隐藏问题。4.5 常见问题速查表症状可能原因修复办法结果中出现[2, 1]错序处理 2 后curr提前推进交换后保持curr不变数组末尾残留 0 或 1循环边界写成curr p2改成curr p2最终数组开头不是 00 分支与 1 分支重叠处理用else if确保互斥全 2 数组运行异常初始化p2忘记减一检查p2初始值是否等于n-1交换时出现越界没有在循环条件里限制curr p2确保循环体只在待处理区域操作这个速查表是实战排错时最直接的参考。如果你在跑测试时看到自己的输出跟预期只差一位几乎都能从上面四条里找到对应原因。5. 从颜色分类延伸到更多场景这思路的价值远不止一道题5.1 面试官最常问的变体问题荷兰国旗问题的核心是“把三类元素分成三个区间”所以面试官围绕它做变体非常顺手。最经典的变体包括把 0、1、2 换成负数、零、正数要求负数在前、零居中、正数在后把颜色换成对象上的某个枚举值要求按枚举顺序分区。还有一类变体是四类元素分区这时单次三指针就不够了。通常做法是先做一趟把小于某个阈值的放左、其余放右再对右侧做一次三指针分区。复杂度仍然保持 O(n)但代码量会明显增加。面试官问这类问题的意图是想看你能否把“三指针”抽象成“多轮分区”的通用能力。关于稳定性的变体也经常出现如果要求 0、1、2 在各自区域内保持原本的先后顺序那就要引入别的思路了比如稳定分区算法或者额外空间。荷兰国旗的双指针交换天然不保证稳定性这一点你最好提前想清楚别在面试中被问到时当场卡壳。5.2 工程里的真实应用场景有人觉得双指针分区只存在于算法题里其实工程中到处都有它的影子。快速排序的核心partition就是典型例子选取一个基准值把数组分成小于基准和大于基准两个区域三路快速排序则直接采用了荷兰国旗的“三区间”思想把等于基准值的元素单独归为一段这样遇到大量重复元素时性能非常显著。我做一个模拟项目 X 时曾经处理过一批订单状态标签要求界面上把“待支付”“已支付”“已取消”三类订单按固定顺序分组展示。后端返回的数据是混着的不想额外构建多个列表再拼接就用双指针思路在原列表上原地重排一段内存都不用多开销。那是我第一次在真实业务代码里用到荷兰国旗解法体验是代码量不大但边界和不变式必须写对否则数据错乱很难排查。另一个贴近生活的例子是很多文件管理器里“按类型排列”的逻辑图片归图片文档归文档压缩包归压缩包。如果底层接口恰好返回的是混合列表用这种分区思想就能在不新建大量临时容器的前提下完成整理。5.3 为什么这道题值得你反复刷几遍我自己的刷题经验是这种“看起来简单、边界水很深”的题最值得重复做。第一遍你可能背下代码第二遍你会发现核心其实是循环不变量第三遍你会主动联想到快排分区、滑动窗口、链表快慢指针等更广泛的场景。尤其对于准备面试的人建议隔一周就把这道题重新在白纸上写一遍不用看任何参考代码。写的过程中问自己三个问题三个指针分别维护什么区间为什么处理 2 后不需要移动curr循环条件为什么必须是curr p2而不是curr p2能把这三个问题讲清楚这道题才算真正过关。从我个人多年的使用感受来说“颜色分类”这道题最妙的地方就在于它把递归和复杂数据结构全部剥掉只留下最纯粹的数组操作思维。你在这里掌握的“分区-交换-推进”节奏在后面学习快速排序、归并排序、滑动窗口、甚至是内存管理里的页替换算法时都会反复遇到。刷题不能只图过题数把一道经典题吃透、能在纸上默写出来、能给同事讲明白比刷十道同类型题目更有实际价值。