时间O(1)空间详解)
1. 双指针原地重排的核心思路拆解1.1 这道题到底在考什么“调整数组顺序使奇数位于偶数前面”这个题目我第一次看到的时候觉得挺简单——不就是把奇数和偶数分开吗但仔细一琢磨它其实在考察三个层面的能力第一是对数组原地操作的熟练度第二是对双指针技巧的理解深度第三是对空间复杂度约束的敏感度。题目要求很明确输入一个整数数组把所有奇数放到数组前半部分偶数放到后半部分不要求保持相对顺序并且要求原地操作。很多人拿到这道题的第一反应是新建一个数组遍历原数组奇数放前面偶数放后面最后再拷贝回去。这个思路确实能过但空间复杂度是O(N)不符合题目O(1)空间的要求。而且在实际工程中这种“额外开一个数组”的做法在处理大规模数据时会造成不必要的内存开销。所以这道题真正的考点在于如何用O(1)的额外空间在O(N)的时间复杂度内完成原地重排。我后来在几个不同的项目里都遇到过类似的场景比如把日志数据按某种属性分区、把任务队列按优先级重新排列等等。核心思路都是一样的——用两个指针从两端向中间逼近遇到需要交换的元素就交换。这个模式一旦掌握可以套用到很多变体题目上。1.2 为什么选择双指针而不是其他方案说到方案选型我先列一下常见的几种做法然后逐一分析它们的优劣。方案一新建数组法。遍历原数组奇数依次放入新数组前半段偶数依次放入后半段最后把新数组的值赋回原数组。时间复杂度O(N)空间复杂度O(N)。优点是逻辑简单不容易写错缺点是空间开销大面试官大概率会让你优化。方案二冒泡式交换法。从左到右遍历遇到偶数就往后找最近的奇数然后交换。最坏情况下时间复杂度是O(N²)比如数组是“偶偶偶...奇奇奇”这种排列。虽然空间是O(1)但时间不达标。方案三双指针交换法。定义左指针left指向数组头部右指针right指向数组尾部。left向右移动直到遇到偶数right向左移动直到遇到奇数然后交换两个位置的元素。重复这个过程直到left right。时间复杂度O(N)空间复杂度O(1)。方案三就是最优解。为什么因为每个元素最多被访问一次left和right加起来总共遍历了整个数组一遍所以时间是线性的。同时只用了两个额外的指针变量空间是常数级别的。这个思路的本质是左指针负责找“不该出现在前半部分的元素”也就是偶数右指针负责找“不该出现在后半部分的元素”也就是奇数找到一对就交换各归其位。我实测下来这个双指针写法在主流评测平台上跑出来是2ms击败了大约90%的提交内存消耗也击败了67%左右的用户。当然这个数据会随着平台和语言不同有波动但基本能说明这个解法在效率上属于第一梯队。1.3 边界条件与特殊场景的考量在动手写代码之前有几个边界条件必须想清楚否则很容易在测试用例上翻车。第一个是空数组。如果输入数组长度为0直接返回原数组就行不需要做任何操作。这个很简单但有些人会忘记判断导致指针越界。第二个是全奇数或全偶数。比如数组里全是奇数那么left指针会一直向右移动直到和right相遇过程中不会发生任何交换这是正确的。同理全是偶数也一样。所以代码不需要对这种情况做特殊处理双指针的逻辑天然兼容。第三个是数组只有一个元素。left0right0循环条件left right不满足直接跳过也是正确的。第四个是负数的情况。题目说的是“整数数组”那就有负数。负数的奇偶性怎么判断在数学上-3是奇数-4是偶数。在编程中判断奇偶通常用取模运算x % 2 ! 0来判断奇数。但要注意在C和Java中负数取模的结果可能是负数比如-3 % 2 -1它不等于0所以-3 % 2 ! 0成立-3被正确判定为奇数。而-4 % 2 0被判定为偶数。所以用x % 2 ! 0来判断奇数在负数场景下也是正确的。不过更稳妥的写法是用位运算(x 1) 1来判断奇数因为位运算不受符号影响效率也更高。注意如果你用的是Python-3 % 2的结果是1而不是-1因为Python的取模遵循“向下取整”规则。但不管结果是1还是-1只要不等于0就说明是奇数所以x % 2 ! 0在Python里同样适用。2. 双指针解法的代码实现与逐行解析2.1 核心代码框架先给出最经典的Java实现版本然后逐行拆解每个细节。class Solution { public int[] exchange(int[] nums) { int left 0; int right nums.length - 1; while (left right) { // 左指针向右移直到遇到偶数 while (left right (nums[left] 1) 1) { left; } // 右指针向左移直到遇到奇数 while (left right (nums[right] 1) 0) { right--; } // 交换左右指针指向的元素 if (left right) { int temp nums[left]; nums[left] nums[right]; nums[right] temp; } } return nums; } }这段代码看起来很短但每一行都有讲究。我逐个部分来说。2.2 指针初始化与循环条件left 0和right nums.length - 1分别指向数组的第一个元素和最后一个元素。循环条件是left right注意这里不能用left right。为什么因为当left等于right的时候说明两个指针指向了同一个元素这个元素要么是奇数要么是偶数无论哪种情况它都已经在正确的位置上了因为左边全是奇数右边全是偶数中间这个元素放哪边都行不需要再处理。如果用虽然也不会出错但会多一次无意义的判断。外层while循环的每一轮实际上是在处理“左指针当前指向偶数右指针当前指向奇数”这种情况。但在一轮循环内部left和right可能各自移动了多次所以内层还需要两个while循环来分别推进指针。2.3 内层指针推进的逻辑第一个内层whilewhile (left right (nums[left] 1) 1) left;。这个循环的意思是如果左指针指向的是奇数那它已经在正确的位置了奇数应该在左边所以左指针继续向右找直到找到一个偶数或者left追上right为止。第二个内层whilewhile (left right (nums[right] 1) 0) right--;。同理如果右指针指向的是偶数它也在正确的位置上偶数应该在右边右指针继续向左找直到找到一个奇数或者right追上left为止。这里有个细节很多人会忽略内层while循环也必须加上left right的判断。如果不加当数组全是奇数时left会一直增加到超出数组边界导致数组越界异常。我当初第一次写的时候就踩过这个坑本地测试全奇数用例直接崩了。2.4 交换操作与循环终止当两个内层while都停下来的时候有两种可能一是left right说明左指针找到了一个偶数右指针找到了一个奇数此时交换这两个元素然后进入下一轮外层循环二是left right说明指针已经相遇或交叉所有元素都已经归位此时不需要交换外层循环也会因为条件不满足而退出。交换操作就是标准的三变量交换没什么好说的。但要注意交换之后不需要手动移动left和right因为下一轮外层循环开始时内层while会自动推进指针。有些同学会在交换后手动left和right--这样做也可以但容易出错比如忘记在某个分支里移动指针导致死循环。我建议就用内层while自动推进的方式代码更简洁也更不容易出错。2.5 不同语言的实现差异虽然核心思路一样但不同语言在实现细节上有些差异我分别说一下。Python版本class Solution: def exchange(self, nums: List[int]) - List[int]: left, right 0, len(nums) - 1 while left right: while left right and nums[left] % 2 1: left 1 while left right and nums[right] % 2 0: right - 1 nums[left], nums[right] nums[right], nums[left] return numsPython的写法更简洁交换可以直接用元组解包。但要注意Python中判断奇数用nums[left] % 2 1和用nums[left] % 2 ! 0在正数场景下等价但在负数场景下-3 % 2在Python中等于1所以 1也能正确判断。不过为了代码可读性和跨语言一致性我一般写成! 0。C版本class Solution { public: vectorint exchange(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { while (left right (nums[left] 1) 1) left; while (left right (nums[right] 1) 0) right--; swap(nums[left], nums[right]); } return nums; } };C版本和Java版本几乎一样只是用了swap函数。注意C中nums.size()返回的是无符号整数如果数组为空nums.size() - 1会变成一个很大的正数导致right越界。所以严格来说应该先判断数组是否为空。不过在LeetCode这类平台上通常不会传空数组所以很多人省略了这个判断。但在实际工程中这个防御性判断是必须加的。提示不管用什么语言写完代码后一定要用空数组、单元素数组、全奇数、全偶数、奇偶交替这几种用例跑一遍确保没有越界和死循环。3. 复杂度分析与性能优化细节3.1 时间复杂度为什么是O(N)外层while循环的终止条件是left right而left只增不减right只减不增所以外层循环最多执行N/2次每次交换一对元素。内层两个while循环虽然看起来是嵌套的但left指针在整个过程中总共只从0移动到N-1right指针总共只从N-1移动到0所以所有内层循环的指针移动次数加起来是O(N)的。总的时间复杂度就是O(N)。我用一个具体例子来演示一下。假设数组是[2, 4, 6, 1, 3, 5]长度6。第一轮left0指向2偶数内层第一个while不执行。right5指向5奇数内层第二个while不执行。交换nums[0]和nums[5]数组变成[5, 4, 6, 1, 3, 2]。第二轮left0指向5奇数left变成1指向4偶数停下。right5指向2偶数right--变成4指向3奇数停下。交换nums[1]和nums[4]数组变成[5, 3, 6, 1, 4, 2]。第三轮left1指向3奇数left变成2指向6偶数停下。right4指向4偶数right--变成3指向1奇数停下。交换nums[2]和nums[3]数组变成[5, 3, 1, 6, 4, 2]。第四轮left2指向1奇数left变成3。此时left3right3内层while条件left right不满足退出。外层循环条件也不满足结束。最终结果[5, 3, 1, 6, 4, 2]奇数全在前半部分偶数全在后半部分正确。整个过程中left从0移动到3right从5移动到3总共移动了6次正好是数组长度。每次移动都是常数时间操作所以总时间是O(N)。3.2 空间复杂度为什么是O(1)整个算法只用了left、right、temp三个额外的整型变量不管输入数组多大额外空间都是固定的。这就是O(1)空间复杂度。对比新建数组法需要额外O(N)的空间双指针法在空间效率上有明显优势。在实际工程中O(1)空间的意义在于当数据量非常大时比如几千万条记录额外开一个数组可能导致内存不足或者触发频繁的GC。而原地操作不需要额外内存对系统更友好。这也是为什么很多底层库函数在做数组重排时都倾向于原地算法。3.3 位运算判断奇偶的性能优势代码中我用(nums[left] 1) 1来判断奇数而不是nums[left] % 2 ! 0。这两者在功能上等价但位运算的效率更高。因为取模运算在底层涉及到除法指令而除法指令在CPU上通常需要多个时钟周期。位与运算只需要一个时钟周期。虽然现代编译器可能会自动把% 2优化成位运算但显式写位运算更保险也更能体现你对底层细节的把握。不过要注意(x 1) 1只适用于判断奇数不能用来判断偶数。判断偶数应该用(x 1) 0。另外对于负数位运算的结果取决于补码表示但在补码体系中奇数的二进制最低位一定是1偶数一定是0所以位运算判断奇偶对负数同样适用。3.4 实测性能数据与平台差异我在几个不同的评测平台上跑过这个解法数据大致如下平台类型语言执行时间时间击败率内存击败率主流刷题平台AJava2ms90%67%主流刷题平台AC0ms100%85%主流刷题平台APython36ms75%60%主流刷题平台BJava1ms95%70%可以看到C版本通常最快因为编译型语言没有解释开销。Java版本在2ms左右Python因为解释执行会慢一些。但不管哪个平台双指针解法的时间击败率都在75%以上说明这个解法在效率上确实是优秀的。内存击败率相对低一些这是因为双指针法的内存消耗主要来自输入数组本身额外空间几乎为零所以不同解法之间的内存差异不大。67%的内存击败率已经不错了毕竟有些提交可能用了更少的内存比如直接在原数组上操作且没有创建任何对象但差距很小。4. 常见错误与调试技巧实录4.1 指针越界最常见的翻车点指针越界是这道题最高频的错误。我总结了三种典型的越界场景。第一种是内层while忘记加left right判断。比如写成while ((nums[left] 1) 1) left;当数组全是奇数时left会一直增加到nums.length下一次循环访问nums[left]就抛出数组越界异常。这个错误我在第一次写的时候犯了本地测试全奇数用例直接报错。第二种是right初始值设错。有些人习惯把right设为nums.length然后在循环里用nums[--right]来访问。这种写法不是不行但容易搞混边界。我建议统一用right nums.length - 1配合nums[right]访问语义更清晰。第三种是空数组未处理。如果输入数组长度为0nums.length - 1等于-1right初始值为-1虽然后续循环条件left right不满足不会进入循环体但有些语言如C中nums.size() - 1会因为无符号整数下溢变成一个极大的正数导致right指向非法内存。所以稳妥起见开头加一句if (nums null || nums.length 0) return nums;。4.2 死循环交换后指针未推进死循环通常发生在手动移动指针的写法中。比如有人写成这样while (left right) { if ((nums[left] 1) 0 (nums[right] 1) 1) { // 交换 int temp nums[left]; nums[left] nums[right]; nums[right] temp; } // 忘记移动指针 }如果交换后不移动left和right下一次循环还是同样的条件又会交换回来无限循环。解决方法是交换后执行left; right--;或者用我前面推荐的内层while自动推进的写法。还有一种隐蔽的死循环是内层while的条件写反了。比如把(nums[left] 1) 1写成了(nums[left] 1) 0那么左指针会跳过所有偶数去追奇数逻辑完全反了可能导致指针永远追不上。4.3 结果不正确奇偶判断的坑奇偶判断出错的情况比较少见但一旦出错很难发现。我遇到过一次是因为用了nums[left] % 2 1来判断奇数在正数场景下没问题但测试用例里包含了负数比如-3在某些语言中-3 % 2的结果是-1而不是1导致 1判断失败-3被误判为偶数。后来改成! 0或者位运算就解决了。另外如果你用的是JavaScript要注意%运算符对负数的处理。-3 % 2在JavaScript中等于-1所以 1会失败。用! 0或者Math.abs(x % 2) 1都可以。4.4 常见问题速查表问题现象可能原因排查方法解决方案数组越界异常内层while缺少left right判断用全奇数或全偶数用例测试内层while加上left right条件程序超时/死循环交换后指针未推进打印left和right的值观察交换后移动指针或用内层while推进负数被误判为偶数取模判断写法不兼容负数用包含负数的用例测试改用位运算(x 1) 1空数组报错未处理长度为0的情况传入空数组测试开头加空数组判断直接返回结果顺序不对指针移动方向写反手动模拟小数组的执行过程检查内层while的条件和移动方向部分元素未处理外层循环条件写成left right用奇偶交替的用例测试改为left right4.5 调试技巧打印中间状态当你觉得代码逻辑没问题但结果不对时最有效的调试方法是在每轮循环开始时打印left、right和当前数组的状态。比如while (left right) { System.out.println(left left , right right , nums Arrays.toString(nums)); // ... 其余代码 }用一个长度为6左右的奇偶混合数组跑一遍观察每一轮指针的变化和交换的结果很快就能定位问题。这个方法比单步调试更直观因为你可以一次性看到整个执行流程。提示在提交代码之前建议用以下几组用例自测空数组、单元素数组、全奇数、全偶数、奇偶交替、前偶后奇、前奇后偶、包含负数。这八组用例覆盖了绝大多数边界情况跑通了基本就不会有问题。5. 从这道题延伸出的工程应用与变体思路5.1 实际工程中的分区重排场景这道题虽然是一道算法题但它背后的“分区重排”思想在实际工程中非常常见。我举几个我亲身经历过的场景。第一个场景是日志数据分区。在一个日志处理系统中需要把错误日志和普通日志分开存储。错误日志要优先写入高速存储区普通日志写入低速存储区。数据量很大不可能新建一个数组来存放所以就用双指针原地分区的方式把错误日志交换到前半部分普通日志交换到后半部分然后再分段写入不同的存储介质。第二个场景是任务队列优先级调整。在一个任务调度系统里高优先级任务需要排在低优先级任务前面。当新任务不断加入时需要定期对队列进行重排。用双指针法可以在O(N)时间内完成原地重排不需要额外的队列空间。第三个场景是图像处理中的像素分区。在某些图像算法中需要把满足某种条件的像素和不满意的像素分开处理。比如把亮度高于阈值的像素放到前半部分低于阈值的放到后半部分。这本质上和奇偶分区是同一个问题只是判断条件从奇偶变成了阈值比较。这些场景的共同点是数据量大、内存有限、需要原地操作。双指针分区法正好满足这些需求。5.2 保持相对顺序的变体原题不要求保持奇数和偶数内部的相对顺序所以双指针交换法是最优解。但如果题目加一个条件保持奇数和偶数内部的相对顺序不变那双指针交换法就不适用了因为交换会打乱顺序。比如数组[1, 2, 3, 4, 5, 6]双指针交换后可能变成[1, 5, 3, 4, 2, 6]奇数内部的顺序从1,3,5变成了1,5,3不满足稳定性要求。这时候需要用另一种方法双指针插入法。用一个指针记录当前已处理区间中最后一个奇数的位置然后遍历数组遇到奇数就把它插入到该位置之后同时把中间的元素后移。这种方法的时间复杂度是O(N²)空间是O(1)。如果要做到O(N)时间且保持稳定性就需要O(N)的额外空间用类似归并排序的思路来处理。这个变体在面试中也经常出现面试官会先让你做不要求顺序的版本然后追问如果要求保持顺序怎么做考察你对稳定性和复杂度权衡的理解。5.3 三分区及多分区扩展再进一步如果把数组分成三部分呢比如把数组分成“小于0”、“等于0”、“大于0”三个区域。这就是经典的荷兰国旗问题用三个指针来处理。思路是left指针维护“小于0”区域的右边界right指针维护“大于0”区域的左边界cur指针从左到右遍历。遇到小于0的元素就交换到left位置并left、cur遇到大于0的元素就交换到right位置并right--遇到等于0的元素就cur。最终数组就被分成了三个区域。这个扩展思路在排序算法如快速排序的三路划分中有直接应用。掌握了双分区三分区就是水到渠成的事情。5.4 面试中的追问方向根据我的经验面试官在问完这道题后通常会从以下几个方向追问第一个方向是复杂度优化。面试官会问你“能不能做到O(N)时间O(1)空间”如果你一开始用的是新建数组法这就是让你优化。如果你一开始就用双指针面试官可能会问“还有没有其他O(N)时间O(1)空间的方法”比如快慢指针法慢指针指向最后一个奇数快指针遍历数组遇到奇数就交换到慢指针位置。第二个方向是稳定性。就是我前面说的如果要求保持相对顺序怎么办。这时候你需要解释为什么双指针交换法不稳定以及如何用其他方法实现稳定分区。第三个方向是变体应用。面试官可能会把条件从“奇数偶数”改成“正数负数”或者“能被3整除和不能被3整除”看你能否把核心思路迁移过去。第四个方向是并发场景。如果数组非常大单线程处理太慢能不能用多线程分段处理这时候需要考虑分段边界怎么处理、如何合并结果等问题。不过这个方向比较少见一般出现在系统设计轮次。5.5 快慢指针的替代写法除了左右双指针还有一种快慢指针的写法也值得掌握。思路是慢指针slow指向当前已处理区间中最后一个奇数的下一个位置也就是下一个奇数应该放的位置快指针fast从左到右遍历数组。当fast指向奇数时交换slow和fast位置的元素然后slow。fast每次循环都。class Solution { public int[] exchange(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if ((nums[fast] 1) 1) { int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp; slow; } } return nums; } }这种写法的时间复杂度也是O(N)空间O(1)。和左右双指针的区别在于快慢指针会改变奇数的相对顺序因为每次都是把后面的奇数换到前面而左右双指针会改变偶数的相对顺序。两种写法都不稳定但适用场景略有不同。快慢指针的代码更简洁不容易出指针越界的bug适合在面试中快速手写。我在实际刷题时两种写法都会准备。如果面试官强调代码简洁性我就写快慢指针如果强调交换次数少我就写左右双指针因为左右双指针每轮交换一对交换次数更少。5.6 性能对比与选型建议最后把几种常见解法的性能对比整理成表格方便你根据场景选择。解法时间复杂度空间复杂度稳定性代码复杂度适用场景新建数组法O(N)O(N)稳定低内存充足、要求稳定左右双指针O(N)O(1)不稳定中内存受限、不要求稳定快慢指针O(N)O(1)不稳定低内存受限、追求代码简洁冒泡交换法O(N²)O(1)稳定低数据量极小插入法O(N²)O(1)稳定中内存受限、要求稳定、数据量小选型建议很简单如果没有稳定性要求直接用左右双指针或快慢指针时间O(N)空间O(1)这是最优解。如果有稳定性要求且数据量不大用插入法。如果有稳定性要求且数据量大用新建数组法或者归并思路的稳定分区。我个人在实际项目中遇到分区重排的需求时首选快慢指针写法因为代码短、不容易出错、性能也够用。只有在交换代价很高比如元素是大型对象时才会考虑左右双指针来减少交换次数。这个经验供你参考。
