荷兰国旗问题：三指针实现O(n)原地排序的LeetCode 75题解析

先说说这道题吧。LeetCode 75. Sort Colors也就是常说的荷兰国旗问题几乎是我在模拟面试里必问的一道题。原因很简单它表面上是个排序题但真正考察的是能不能跳出调用排序函数的惯性思维在O(n)时间、O(1)空间里完成数组的原地划分。很多候选人一上来就说用快排或者计数排序思路本身没错但距离题目想考的点就差了一层。这篇就来完整拆解这道题从暴力解到最优解把每一步的来龙去脉讲清楚。题目本身不复杂给定一个只包含0、1、2的数组原地排序使得所有0在最前面所有1在中间所有2在最后面。不能使用库函数。看起来就像是个简化版的排序问题但实际上它的约束条件直接指向了一个特定的解法——三指针扫描。我们先从题面细节和边界条件入手把输入输出的坑都摸清楚。1. 题面里藏着的约束不能有额外空间也不能用内置排序1.1 一句话概括问题本质LeetCode 75的原始描述是给定一个包含红色、白色、蓝色一共n个元素的数组原地对它们排序使得相同颜色的元素相邻并按红、白、蓝顺序排列。对应到数字就是0、1、2。我第一次看到这个问题的时候第一反应是这不就是个排序吗然后下意识就想用Arrays.sort()但仔细一看题目要求才发现它明确说了不能使用库函数而且要求一趟扫描完成排序。这两个限制直接把调用排序接口这条路堵死了也把时间复杂度压到了O(n)。1.2 为什么空间复杂度也是硬指标题目还要求原地排序意味着借助一个新数组来统计0、1、2的数量再回填这种思路虽然正确但空间上就不满足要求了。这里的原地不是随便说说的——如果允许O(n)额外空间那这道题就变成了一道简单的计数题完全失去了训练价值。实际上我从这道题里悟出的一个道理是很多LeetCode题目的约束条件就是提示。不能使用额外空间暗示了要用交换而不是复制要求一趟扫描暗示了要用指针而不是分治。你如果能把题目里的每个限制条件翻译成对应的算法设计思路解题方向基本就锁定了一半。1.3 边界条件空数组、单元素数组、全0全1全2做题先看边界这是一个好习惯。Sort Colors的边界条件主要就三种数组长度为0或1不需要任何操作直接返回。数组里只有一种数字比如全是0那不管怎么扫描都已经是排好序的。数组里数字种类不全比如只有0和2没有1这时候指针移动的逻辑要能正确处理。这些边界条件看着简单但正是它们最容易暴露代码逻辑的漏洞。我自己写三指针解法的时候就曾经在全是2的用例上卡住过后面会详细讲这个坑。2. 从暴力解到最优解每种思路的性价比分析先别急着上最优解。把这道题的所有可行思路串一遍你会发现一条清晰的演进路径暴力排序 → 计数排序 → 双指针 → 三指针。每一步都是对前一步的优化理解了这条路径才算真正吃透了这道题。2.1 最直接的思路直接调用排序函数最简单粗暴的解法就是调用语言内置的排序函数比如Python的sorted()一行代码搞定class Solution: def sortColors(self, nums: List[int]) - None: nums.sort()或者C的std::sortclass Solution { public: void sortColors(vectorint nums) { sort(nums.begin(), nums.end()); } };这个解法在工程实践里其实是正确的选择——既然语言已经提供了稳定、高效的排序实现为什么要自己造轮子但LeetCode这道题明确禁止使用库函数而且在面试场景下如果你直接调sort面试官会认为你缺乏对算法底层的理解。这里我要多说一句我自己面试别人的时候如果候选人一上来就调库函数我不会直接判负而是会追问一句那你能手写一个O(n)的解法吗如果他能说出来计数排序或三指针说明他理解复杂度如果只会调库那道题就到此为止了。所以刷题不能只满足于能过用例要习惯性地问自己有没有更优的解法为什么这道题是这样的限制2.2 常规思路计数排序遍历两遍不能用库函数那自己写一个呢最直观的想法是先遍历一遍数组数一数0、1、2各有多少个然后再遍历一遍数组把对应数量的数字回填进去。这就是计数排序的思路。class Solution: def sortColors(self, nums: List[int]) - None: count [0, 0, 0] for num in nums: count[num] 1 i 0 for val in range(3): for _ in range(count[val]): nums[i] val i 1时间复杂度O(n)空间复杂度O(1)——因为计数数组大小固定为3不随n增长。从复杂度的角度来看这个解法已经完全达标了。那这道题还有什么好纠结的问题在于它遍历了两次而题目要求是一趟扫描。如果你只是想在LeetCode上把题过了计数排序没问题但如果面试官明确说了one pass计数排序就过不了这关。另一个潜在问题更隐蔽计数排序假设了颜色种类是固定的0、1、2三种。如果面试官把题目扩展成K种颜色排序计数排序的计数数组大小就变成K了空间复杂度变成O(K)。这时候虽然K可能还是常数但解法就失去了通用性。相比之下三指针解法的思想可以顺理成章地迁移到三路快排而计数排序迁移不到那里。2.3 双指针的探索为什么两个指针不够在引出三指针之前很多人会先尝试双指针。比如维护一个left指针指向数组开头right指针指向数组结尾然后遍历数组——遇到0就扔到左边遇到2就扔到右边。这个思路方向是对的但实际编码时会发现一个问题你用一个指针i从左往右遍历遇到0和left交换遇到2和right交换那i什么时候前进什么时候不动如果交换回来的数字是2i还能继续走吗这就是双指针不够用的根本原因你用一个指针i同时承担遍历和分类两个职责当i和right交换之后它拿到的数字可能是0、1、2中的任何一个这时候如果贸然前进就可能错过对交换回来数字的处理。所以必须引入一个中间指针让0和2的交换互不干扰——这就是三指针解法的由来。三指针并不是凭空想出来的它是荷兰国旗问题的标准解法由Dijkstra提出——没错就是那个写《算法导论》里Dijkstra算法的同一个人。他的核心洞察是数组经过扫描后可以被划分成四个区域每个区域由指针边界清晰地隔开。3. 核心解法三指针的循环不变量与移动规则3.1 四个区域的划分逻辑三指针解法会维护三个指针left也常叫low、mid也常叫i、right也常叫high。它们的含义如下[0, left)全部是0[left, mid)全部是1[mid, right]未扫描的未知区域(right, n-1]全部是2这四个区域加起来正好覆盖整个数组。初始化时left 0mid 0right n-1。也就是说0区域和1区域都是空的整个数组都是未扫描区域2区域也是空的。这符合我们的直觉扫描还没开始什么分类都没做。随着扫描进行mid会不断向右移动right会不断向左收缩left会随着0的发现而向右扩张。当mid超过right时未扫描区域消失所有元素都归入了0、1、2三个区域排序完成。3.2 while循环里的三种情况三指针的核心逻辑写出来极其简洁但我强烈建议每个人都能自己推导一遍而不是死记硬背。初始化left, mid, right 0, 0, len(nums) - 1循环条件是mid right因为当mid right时说明未知区域已经被扫描完了。在循环体内我们只看nums[mid]的值分三种情况处理情况一nums[mid] 0这说明mid当前指到的元素应该归入0区。做法是交换nums[left]和nums[mid]然后left 1mid 1。为什么mid也要加一因为交换过来的nums[left]要么是1要么是0。如果left mid说明当前元素本来就该在0区交换后mid元素还是0直接前进没问题如果left mid说明nums[left]原本在1区的位置交换后mid拿到的一定是1所以可以把mid直接往前推进。不管哪种情况交换后mid位置的值都已经被处理过了mid继续前进是安全的。情况二nums[mid] 1这说明当前元素本来就该在1区什么都不用做直接mid 1继续扫描下一个。情况三nums[mid] 2这说明当前元素应该归入2区。做法是交换nums[mid]和nums[right]然后right - 1。注意这里mid不需要加一。因为从right交换过来的值是未知的可能是0、1、2中的任何一个。如果交换过来的是0或2mid原地不动可以继续处理如果贸然mid 1就可能漏掉对这个元素的分类导致0或2留在1区。这几乎是所有人写这道题时最容易踩的坑后文我会专门用调试案例来说明如果不这样写会出什么错。3.3 为什么一定要while mid right而不是while mid right还有一个容易含糊的细节循环条件是mid right还是mid right先说结论应该用mid right。原因是当mid right时当前mid所指的这个元素还处于未扫描区域需要被处理。如果条件写成mid right循环会提前终止mid right位置的那个元素就没有被分类。举个例子数组[2, 0, 1]。初始left0, mid0, right2。第一步nums[0] 2交换nums[0]和nums[2]数组变成[1, 0, 2]right变成1。此时mid0, right1。第二步nums[0] 1mid变成1。此时mid1, right1。第三步mid right如果循环条件是mid right这里就退出了。但nums[1] 0还没被处理最终结果会错误地输出[1, 0, 2]。正确做法循环条件mid right进入第三步nums[1] 0交换nums[0]和nums[1]数组变成[0, 1, 2]left1, mid2此时mid right退出循环结果正确。这个坑我在代码review时见过太多次了因为它不是每次用例都会触发只有恰好让mid right时指向非1元素才会暴露。写的时候务必留个心眼。3.4 完整代码实现Python版本class Solution: def sortColors(self, nums: List[int]) - None: left, mid, right 0, 0, len(nums) - 1 while mid right: if nums[mid] 0: nums[left], nums[mid] nums[mid], nums[left] left 1 mid 1 elif nums[mid] 1: mid 1 else: # nums[mid] 2 nums[mid], nums[right] nums[right], nums[mid] right - 1C版本class Solution { public: void sortColors(vectorint nums) { int left 0, mid 0, right nums.size() - 1; while (mid right) { if (nums[mid] 0) { swap(nums[left], nums[mid]); } else if (nums[mid] 1) { mid; } else { swap(nums[mid], nums[right--]); } } } };这里有个值得注意的编码细节C的swap(nums[left], nums[mid])虽然简洁但可读性稍差如果是团队协作建议拆成三行写方便review的人理解。LeetCode的提交不影响但工程习惯要养好。3.5 时间复杂度与空间复杂度时间复杂度while循环里mid从0最多走到rightright从n-1最多走到0每个元素最多被访问一次整体O(n)。空间复杂度只用了三个整型变量O(1)。这里有个很有意思的点这个算法是不稳定的。什么意思如果数组里有两个值相同的1它们的相对顺序可能会在交换中改变。不过这道题的输入是0、1、2这种标量稳定性没有实际意义——因为0和0、1和1之间根本分不清谁是谁。但如果把这道题的思想迁移到对象排序上比如按颜色给对象分组稳定性就需要纳入考虑了。面试时如果把这一点主动说出来通常会是加分项。4. 边界条件与常见错误的完整复盘4.1 手推一遍完整过程以[2,0,2,1,1,0]为例纸上得来终觉浅我们还是用一个完整例子手动跑一遍算法。输入[2,0,2,1,1,0]。初始状态left0, mid0, right5数组为[2, 0, 2, 1, 1, 0]。步骤midnums[mid]操作数组状态leftright102交换nums[0]和nums[5][0, 0, 2, 1, 1, 2]04200交换nums[0]和nums[0][0, 0, 2, 1, 1, 2]14310交换nums[1]和nums[1][0, 0, 2, 1, 1, 2]24422交换nums[2]和nums[4][0, 0, 1, 1, 2, 2]23521无操作[0, 0, 1, 1, 2, 2]23631无操作[0, 0, 1, 1, 2, 2]23第6步结束后mid4right3mid right循环退出。数组已经排好序了[0, 0, 1, 1, 2, 2]。注意第2步和第3步当数组本身是0的时候交换nums[left]和nums[mid]是同一个位置的交换没有任何效果但left和mid照常前进。这是正确的——此时0已经在自己应该在的位置了指针只需要继续移动。4.2 常见错误一nums[mid] 2时错误地让mid自增这是出现频率最高的错误。错误代码长这样while mid right: if nums[mid] 0: nums[left], nums[mid] nums[mid], nums[left] left 1 mid 1 elif nums[mid] 1: mid 1 else: nums[mid], nums[right] nums[right], nums[mid] right - 1 mid 1 # 这句是错的为什么是错的因为交换到mid位置上的元素可能是0或2需要在这个位置再处理一次。如果直接mid 1这个元素就会被当作已经分类好的1从而漏掉。用一个具体例子验证[1, 2, 0]。初始left0, mid0, right2。第一步nums[0] 1mid 1。此时mid1。第二步nums[1] 2交换nums[1]和nums[2]数组变成[1, 0, 2]right1mid1变成2。第三步mid2, right1mid right循环退出。最终结果是[1, 0, 2]显然是错的那个0本应该在1的前面。正确写法是交换后mid保持不变else: nums[mid], nums[right] nums[right], nums[mid] right - 1 # mid 保持不动4.3 常见错误二把nums[mid] 0时mid自增忘了有一个变体错误更隐蔽有些人在处理0的时候没有让mid自增。if nums[mid] 0: nums[left], nums[mid] nums[mid], nums[left] left 1 # 忘了 mid 1这会怎样假设数组是[0, 1, 2]初始left0, mid0, right2。第一步nums[0] 0交换自身left变成1mid保持0。第二步nums[0] 0还是0交换自身left变成2mid保持0。第三步nums[0] 0还是0left变成3mid保持0。mid永远停留在0left一直在自增这个循环永远不会处理到1和2会形成死循环。所以处理0时left和mid必须成对自增除非你做了等价替换。4.4 常见错误三边界判断用了mid right我在3.3节已经详细推导过这里再给一个完整的反例[2, 1, 0]。使用while mid right初始left0, mid0, right2。第一步nums[0] 2交换nums[0]和nums[2]数组变成[0, 1, 2]right1。第二步nums[0] 0交换nums[0]和nums[0]left1, mid1。第三步此时mid1right1mid right不成立循环退出。数组是[0, 1, 2]看起来是正确的但这是个巧合中的巧合。换一个输入[2, 0, 1]就不行了这个例子我在3.3节已经演示过最终会错误地输出[1, 0, 2]。结论很明确写这个循环时直接用while mid right不用犹豫。4.5 如何快速自测几个必测用例我自己刷题、写算法的时候会积累一些必测用例清单这道题的核心用例有[]空数组直接返回。[0]单元素0。[1]单元素1。[2]单元素2。[0, 1, 2]已经是正序。[2, 1, 0]完全逆序。[2, 0, 1]最容易触发mid rightbug的用例。[2, 0, 2, 1, 1, 0]中等长度混合。[0, 0, 0]全0。[1, 1, 1]全1。[2, 2, 2]全2。如果这组用例都能通过基本可以放心提交了。5. 从Sort Colors到三路快排这道题的思想迁移5.1 三路快排的核心思想如果只把Sort Colors当作一道题来刷刷完就过去了那收获就太少了。我在实际工程和面试中反复体会到这道题背后的三指针分区思想往大了说可以延伸到三路快排3-Way QuickSort这是处理大量重复键的利器。传统快排的partition把数组分成小于pivot和大于等于pivot两个区域但遇到大量重复元素时会退化比如数组全是同一个值快排会做大量无意义的交换和递归。三路快排的分区则把数组分成三块小于pivot、等于pivot、大于pivot。对于重复键多的数组等于pivot的区域可以不再参与递归从而大幅减少递归深度和交换次数。Sort Colors本质上就是pivot为1的三路快排分区0区是小于pivot的元素1区是等于pivot的元素2区是大于pivot的元素。如果理解了Sort Colors的三指针逻辑三路快排的partition就不难写了。void quickSort3Way(vectorint arr, int lo, int hi) { if (lo hi) return; int lt lo, i lo 1, gt hi; int pivot arr[lo]; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); } else if (arr[i] pivot) { swap(arr[i], arr[gt--]); } else { i; } } quickSort3Way(arr, lo, lt - 1); quickSort3Way(arr, gt 1, hi); }注意看这个代码和Sort Colors的对应关系lt对应lefti对应midgt对应rightarr[i] pivot对应nums[mid] 0arr[i] pivot对应nums[mid] 2arr[i] pivot对应nums[mid] 1。几乎是同一套逻辑的平移。5.2 变种题K种颜色排序面试官可能顺着这道题往下问如果数组里有K种颜色数字范围从0到K-1怎么排序如果K是常数计数排序依然是最优的O(n)时间、O(K)空间。但如果要求O(1)空间呢这里有个分治的思路可以借鉴快速排序的partition思想选定一个中间值把数组分成小于等于中间值和大于中间值两部分递归处理。这个过程的时间复杂度是O(n log K)空间复杂度O(log K)递归栈。另一种思路是桶排序但需要额外空间。所以K种颜色的问题实际上在考察你能不能接受用时间换空间或用空间换时间的权衡。这就是我在面试中比较看重的点——候选人能否清晰地表达各种方案的复杂度取舍。5.3 工程场景中的实际应用有人可能会问工程里真的会有人手写这种排序吗答案是绝大多数时候不会std::sort已经足够好。但三路划分思想在很多地方有实际应用比如数据库索引的分区按某个字段的值把数据分成多个区间再分别处理避免全表扫描。流式数据处理数据源源不断地到来需要实时按照类别分流三指针的思路可以保证每个数据只需要O(1)的额外空间。图像处理中的颜色量化把像素点的颜色值按通道分类用类似的方法把颜色区间分割出来。5.4 一道思路相似的LeetCode题移动零和Sort Colors思路最接近的题目是LeetCode 283. Move Zeroes。那道题要求把数组里的0全部移到末尾非0元素保持原顺序。它同样要求原地操作思路也是双指针一个指针遍历一个指针指向下一个非0元素应该放置的位置。如果把283这道题做一遍再回来对比75题会发现一个有趣的递进283是两种元素的分类0和非0用双指针就够了75是三种元素的分类0、1、2双指针不够需要三指针。这个递进能帮助你形成一个直观认识——处理K种元素的分类大体上需要K-1或K个指针具体取决于分类策略。6. 实战演练与复盘我用三个维度评估这道题的掌握程度6.1 维度一能不能从零推导刷题不是背题。我建议你合上代码拿一张白纸从四个区域的划分这个定义出发自己推导一遍三个指针的移动规则。如果你能完成这个过程说明你理解了算法的来源如果只能默写代码换一个参数比如pivot从1变成2就可能出错。我自己带新人时常用一个方法把题目改成把所有2放最前面0在最后1在中间也就是把目标顺序换一下看他能不能快速调整代码。大部分死记硬背的候选人会卡住而真正理解的候选人只需要改动一个判断分支的顺序。6.2 维度二能不能解释循环不变式循环不变式听起来很学术但其实是检验你理解深度最简单的问题。你可以问自己在每一轮循环开始时以下三个条件是否恒成立区间[0, left)内所有元素都是0区间[left, mid)内所有元素都是1区间(right, n-1]内所有元素都是2如果循环体内每个分支都正确维护了这三个条件那循环结束时mid right意味着未扫描区域为空此时整个数组已经被三个区间完整覆盖排序自然完成。这种证明方式就是算法导论里说的循环不变式。把这个证明思路写进代码注释里可以让后来维护代码的人一眼就明白为什么这样写是对的。我在团队里review这类代码时最怕看到没有任何注释的指针操作光靠人脑推理太容易出错了。6.3 维度三能不能现场讲清楚为什么交换2后mid不能动这个问题几乎是我模拟面试必问的follow-up。如果你能在30秒内给出清晰解释——因为交换回来的元素没有被检查过它可能是0、1、2中的任意一个所以必须留在mid位置再走一轮循环——这道题就算真过关了。顺便说一句如果候选人能把这种为什么讲清楚我会觉得他对基础算法是有敬畏心的。很多人刷了200题但每一道题都只刷个AC就过从不追问他背后的原理这样在真正的面试压力下很容露馅。7. 关于Sort Colors的几个高频追问与经验心得7.1 如果数组里包含0以外的负数呢原题限定了元素只能取值0、1、2所以不需要考虑其他情况。但如果你想把这个解法泛化可以处理任意三个固定值的情况比如把目标排列顺序抽象成一个映射函数。不过那就不是Sort Colors了而是更一般化的三分类问题。做题的时候先想清楚题目给定的约束再动手不要过度设计。7.2 三指针和双指针在空间上的本质区别三指针不是比双指针多了一个变量而已它背后的思想差异是双指针通常处理两类元素的划分比如0和非0三指针才能处理三类元素的划分。如果给你四种颜色通常需要四指针或者用递归/分治的思路来处理。理解这个递进关系比多刷十道题都有用。7.3 个人经验我建议你怎么刷这道题如果把这道题当作面试准备的一部分我的建议是分三步走先独立做一遍不限时把计数排序和双指针的边界问题都踩一遍。再看三指针解法重点看2的交换为什么不能移动mid。最后合上代码用[2, 0, 1]这个用例手推整个流程直到不需要看代码也能写对。我见过不少人在第一遍就能AC但过两周再写又写错了。原因就是没有理解循环不变式纯粹在背代码。这道题值得你多花一点时间把每一步的为什么想透收益远大于刷十道简单题。7.4 一个面试加分的小技巧面试官问完解法后如果你能主动补充一句这个解法就是荷兰国旗问题的三指针版本Dijkstra提出的它最大的优点是不需要额外空间一趟扫描完成分区通常能留下不错的印象。这不算炫技而是表现出你对经典算法的了解面广并且知道它的来龙去脉。说回我自己当年第一次做这道题的时候也翻过车——把mid right写成了mid right测试用例[2, 0, 1]直接报错。还好当时不厌其烦地跟用例调试亲手抓出了那个藏在边界里的问题之后几年再写这道题都再也没有错过。希望能帮助你一次就写对少走我当年走过的这段弯路。