★ FEATURED ARTICLE 如果你和我一样刷剑指offer时是按题号一路点下去的看到“调整数组顺序使奇数位于偶数前面二”这种标题第一反应大概率是这不就是双指针扫一遍然后交换然后要么点了提交发现用例过不了要么在面试现场听到面试官补了一句“要求奇数之间、偶数之间保持原有相对顺序”当场就愣住了。我当年就栽过一次白板前先把双指针写得飞快结果面试官追问“你保证稳定吗”我盯着自己的代码沉默了十秒。这篇文章就把这道题从大众版到进阶版彻底拆开讲清楚三套方案的原理、代码和取舍也把面试官顺着这题常追问的几个点一起聊透。适合正在刷题准备面试的人也适合想真正理解“稳定分区”这个底层概念的开发者。1. 题目到底在问什么先分清“大众版”和“二”的差别1.1 原题与进阶版的文本差异原题第一版描述很简单输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有奇数位于数组的前半部分所有偶数位于数组的后半部分。绝大多数博客给出的解法就是首尾双指针加交换但这种解法只解决“分区”问题不解决“稳定性”问题。进阶版也就是标题里的“二”通常会在题干里多出一句话调整之后奇数和奇数之间、偶数和偶数之间的相对位置保持不变。别小看这半句话它直接把很多看起来很漂亮的解法淘汰掉了。题号在不同平台会有差异有的地方标剑指offer 21有的地方标68还有的OJ平台上分成函数题和拓展题。我自己的习惯是从来不记题号只看题干里有没有“相对位置不变”这几个字样。有就是稳定版没有才是大众版。用一个具体例子说明差别。输入数组[2, 4, 1, 3, 5]大众版只要求最终左边全是奇数、右边全是偶数所以[5, 3, 1, 4, 2]这种结果也算对进阶版则必须输出[1, 3, 5, 2, 4]因为原数组里奇数出现的顺序是1、3、5偶数出现的顺序是2、4调整后各自内部的先后顺序不能乱。这个本质区别就是“只做分区”和“做稳定分区”的区别。1.2 稳定性的边界条件很多刚接触这道题的人会对“稳定性”这个概念有点模糊我多说两句。稳定性的要求不是让奇数段整体有序也不是让偶数段整体有序而是只要求“各自保持原数组里的先后次序”。比如原数组是[7, 1, 3]这三个奇数的出现顺序是7、1、3调整之后奇数段必须是[7, 1, 3]不能变成[1, 3, 7]。偶数段同理。奇数段和偶数段之间因为天然要分割开所以不存在跨段比较的要求。为什么实际业务里会提这种要求因为数组里的元素往往不只是一个孤零零的整数它可能是个对象、一条记录、一个节点附带其他业务字段。奇偶只是筛选条件原始的先后顺序可能代表优先级、时间戳或者某种业务语义。如果一次“调整顺序”把这些顺序打乱了后面再要恢复就很麻烦。这也是为什么面试官喜欢在简单题后面加一句“保持相对顺序”考察的不是你会不会写双指针而是你有没有意识到“稳定”这两个字的分量。1.3 先给结论三套方案的复杂度地图在展开代码之前我先把这个题的整体方案地图摆出来后面每一节再逐个拆。很多人在网上搜这道题会看到各种解法但搞不清它们之间的关系其实就三种方案时间复杂度空间复杂度是否稳定双指针交换O(n)O(1)否辅助数组两趟扫描O(n)O(n)是原地整体右移O(n²)O(1)是面试时最优的答题顺序是先用一句话讲清楚“不要求稳定双指针O(n)解决要求稳定可以用辅助数组O(n)时间O(n)空间也可以原地移动O(n²)时间O(1)空间”。这一句话说完面试官就知道你不是背题而是真的想清楚了原理。2. 双指针解法为什么能过大众版却过不了“二”2.1 算法流程与代码双指针的思路非常直观用两个指针从数组两端往中间夹逼。左指针left从头往右找偶数右指针right从尾往左找奇数找到之后交换然后继续。循环终止条件是left right。void reorderOddEven(vectorint nums) { int left 0; int right (int)nums.size() - 1; while (left right) { // 左指针向右找偶数 while (left right (nums[left] 1)) { left; } // 右指针向左找奇数 while (left right !(nums[right] 1)) { --right; } if (left right) { swap(nums[left], nums[right]); } } }这里有两个细节我必须强调。第一个细节内层循环一定要加上left right的判断。我第一次写这个代码的时候偷懒没加结果是数组全为偶数时右指针一路向左越界减成负数直接数组越界。笔试OJ上这个问题还不太容易暴露但面试现场白板上写出来面试官一眼就能揪住。第二个细节right的类型一定要写成int不要用size_t。nums.size()返回无符号数如果数组为空nums.size() - 1会得到一个巨大的无符号整数而不是-1循环逻辑直接乱套。这种类型混用问题在C里尤其常见刷题时可以图省事但心里一定要清楚。2.2 一个例子看穿它为什么不稳定我直接用[2, 4, 1, 3, 5]跑一遍双指针你就明白它为什么不满足进阶版要求。初始状态left0指向2偶数right4指向5奇数交换得到[5, 4, 1, 3, 2]。接着 left1指向4偶数right3指向3奇数交换得到[5, 3, 1, 4, 2]。然后 left2指向1奇数left继续右移指向4偶数此时 right2left3left right循环结束。最终结果[5, 3, 1, 4, 2]左边三个确实是奇数右边两个确实是偶数但奇数的顺序从原来的1、3、5变成了5、3、1完全倒转了。原因很简单双指针是首尾配对交换最右边的奇数和最左边的偶数直接互换这一交换就把奇数之间的相对次序打破了。换句话说任何用“远距离直接交换”来分区的方法本质上都会破坏稳定性这不是边界问题而是算法结构决定的。2.3 没有稳定性要求时它就是最优解如果题目确实没有要求“保持相对顺序”双指针解法就是最优解一趟遍历O(n)时间O(1)额外空间代码简洁性能极佳。笔试OJ如果不验证内部顺序只判断奇数集合和偶数集合是否分居两侧这个解法跑得飞快。所以我的定位是双指针解法是“热身答案”用来展示你基础扎实、复杂度敏感但千万不要把它当作这道题的唯一解否则面试官一追问就露馅了。真正的考点在后面两个稳定方案上。3. 稳定版第一套辅助数组两趟扫描3.1 思路与代码稳定版最简单、最不容易出错的解法就是用一个辅助数组做两趟扫描思路浓缩成一句话“第一趟收奇数第二趟收偶数。”第一趟遍历原数组把所有奇数按出现顺序放进结果数组第二趟再遍历原数组把所有偶数按出现顺序放进结果数组。因为两趟遍历都是从左往右走所以每一类数字内部的相对顺序天然就是原始顺序。vectorint reorderStable(const vectorint nums) { vectorint res; res.reserve(nums.size()); for (int x : nums) { if (x 1) { res.push_back(x); } } for (int x : nums) { if (!(x 1)) { res.push_back(x); } } return res; }如果面试题要求原地修改而不是返回新数组最后加一句const_cast是不对的正确做法是接收非const引用然后nums std::move(res);或者nums.swap(res);。我平时在牛客上写这道题一般直接返回新数组因为题面通常不要求原地。这里还有一个细节res.reserve(nums.size())不是可有可无的。如果不提前预留容量push_back过程中vector会反复扩容、搬移数据虽然均摊复杂度还是O(n)但实际常数会大不少。在大数组上测试这两个版本的速度差距能超过一倍。面试时写不写reserve是区分“会写”和“写得好”的细微之处。3.2 稳定性从哪来稳定性在这个方案里是“结构上保证”的不是碰巧成立。第一次扫描从下标0到n-1遍历凡是奇数就依次追加到res尾部。假设原数组里奇数a和b满足a在下标i、b在下标j且ij那么在遍历过程中a一定先于b被收集所以res奇数段里a依然在b前面。偶数段同理。这个方案从头到尾没有发生任何跨越式交换也没有相邻元素对换只是“按原顺序筛选 追加”所以稳定是必然的。有些同学会问这个算排序吗严格说不算排序因为整个过程没有对元素大小做任何比较只是在按某个谓词分组属于分组操作。但它的稳定性和稳定排序的稳定性是同一个概念。理解这一点之后以后遇到“按奇偶分组”“按正负分组”“按是否3的倍数分组”这些变体你都可以条件反射式地秒掉。3.3 空间换时间值不值说句实话工程上这个取舍非常值。一个n大小的vector副本在绝大多数场景下内存完全够用但代码的正确性和可读性提升了一大截。我自己在项目里写到类似的分组逻辑只要能开临时数组一律优先开临时数组等真出现内存瓶颈了再优化也不迟。刷题场景也一样。笔试时间宝贵不要一上来就挑战原地算法先把辅助数组版本写对、跑通再在脑子里过一遍原地版本准备应对面试追问。大部分笔试判题只看最终正确性和时间复杂度不会检查你用了多少额外空间。只有面试官明确说“能不能不用额外空间”你才需要亮出下一套方案。4. 稳定版第二套原地位移用O(n²)时间换O(1)空间4.1 从冒泡交换到整体右移如果面试官追问“能不能不用辅助数组原地实现稳定调整”就需要第二套思路。最直觉的原地稳定做法是模拟冒泡排序从左到右扫描每遇到一个“当前元素是奇数、前一个元素是偶数”的相邻对就把它们交换反复执行直到整个序列没有这种逆序对。这个做法确实能保证稳定本质上是冒泡排序的变体但交换的次数非常多而且白板代码写起来看着也不太优雅。我更推荐另一个思路整体右移。维护一个变量evenStart表示当前已处理区间中第一个连续偶数段的下标。扫描数组时如果遇到奇数就把这个奇数往左“搬”到evenStart位置中间路过的所有元素整体右移一位。奇数段是依次处理出来的所以奇数内部保持原始顺序偶数段只是整体平移所以偶数内部也保持原始顺序。为什么整体右移比连续swap更容易说清楚因为swap一次次做别人的注意力全被“交换”吸引走了而“整体右移一位”一句话就点明了关键不动偶数彼此之间的先后关系。4.2 实现代码与手动模拟void reorderStableInPlace(vectorint nums) { int evenStart -1; int n (int)nums.size(); for (int i 0; i n; i) { if (nums[i] 1) { if (evenStart ! -1) { int tmp nums[i]; for (int j i; j evenStart; --j) { nums[j] nums[j - 1]; } nums[evenStart] tmp; evenStart; } } else if (evenStart -1) { evenStart i; } } }evenStart的语义要理解清楚它记录的是当前“第一个偶数”的位置。只要还没遇到过偶数它保持-1一旦遇到第一个偶数就把它所在下标记录下来。后续如果遇到奇数说明[evenStart, i-1]这一段全是偶数于是把奇数插到 evenStart偶数段整体右移插完之后 evenStart 自增1仍然指向新的第一个偶数。这个不变式是整个算法正确性的核心。用手动模拟验证一下输入[2, 4, 1, 3, 5]inums[i]evenStart处理后数组02偶0[2, 4, 1, 3, 5]14偶0[2, 4, 1, 3, 5]21奇0 → 1[1, 2, 4, 3, 5]33奇1 → 2[1, 3, 2, 4, 5]45奇2 → 3[1, 3, 5, 2, 4]最终结果是[1, 3, 5, 2, 4]与辅助数组版本完全一致。我在白板上第一次手推这个模拟时还犯了一个边界错误移动循环写成j evenStart而不是j evenStart结果nums[evenStart - 1]被当作临时变量踩坏了。所以这里要特别提醒循环结束条件是j evenStart 1结束时nums[evenStart]这个位置已经空出来再放tmp。4.3 什么时候别用原地版原地版的代价是时间复杂度退化到O(n²)。最坏情况是数组前半部分全是偶数、后半部分全是奇数比如[2, 4, 6, 8, 1, 3, 5, 7]每次遇到一个奇数都要把前面越来越长的偶数区间整体右移总移动次数接近n²/2。数据量小的时候无所谓数据量到百万级别就会非常明显。所以面试时你要主动把代价说清楚稳定 原地 O(n)时间在数组上是没有免费午餐的。我一提这个复杂度上界面试官通常都会点头因为这显示你不只会写代码还知道方案在什么场景下会失效。如果数据量很大又要求稳定那就老老实实回退到辅助数组方案多花一倍内存换取O(n)时间是更工程化的选择。5. 面试官顺着这题一定会追问的三个方向5.1 把“是不是奇数”抽成谓词这道题在剑指offer里有个隐藏考点判断逻辑和移动逻辑要解耦。很多讲解版本在讨论移动思路时代码里写死了x 1这个条件。面试官只要把题目换一个字“把负数放前面正数放后面”“把能被3整除的放前面”你就得重新写一遍整个函数这就显得很笨。正确做法是把“是奇数”这个判断抽成一个函数作为参数传进去。C语言风格里最直接的是函数指针bool isOdd(int x) { return (x 1) 1; } void reorderStable(vectorint nums, bool (*pred)(int)) { vectorint res; res.reserve(nums.size()); for (int x : nums) { if (pred(x)) { res.push_back(x); } } for (int x : nums) { if (!pred(x)) { res.push_back(x); } } nums.swap(res); }调用的时候写reorderStable(nums, isOdd);就行。后面无论题目怎么变形只要换一个谓词函数主框架一行都不用动。C里还能用std::functionbool(int)、lambda、模板参数等更现代的方式白板面试时用函数指针最稳妥也最能体现C基础。5.2 判奇偶的隐藏坑负数取模用x % 2 1判断奇数是这道题里最容易翻车的写法。正数没问题但负数会出事-3 % 2的结果是-1不等于1于是-3会被错误地归到偶数里。这个bug在只测正数的OJ上跑不出来面试官只要补一个负数用例立刻翻车。正确写法是位运算x 1因为不论正数负数在补码表示下最低位都是1才表示奇数-3的二进制补码最低位是1所以(-3) 1结果是1。这个知识点看起来很小但在面试里属于“会不会写底层判断”的分水岭很多人就是栽在这种小细节上。我已经不止一次在面试复盘里见到候选人对取模和位运算的区别说不清楚。5.3 从这道题到稳定分区的下界如果面试聊得深还会考到“稳定分区”的算法理论边界。数组上的稳定分区问题朴素实现就是前面说的两条路O(n)时间配O(n)空间或者O(1)空间配O(n²)时间。这也是为什么标准库里stable_partition这类函数在内存充足时优先用额外空间内存紧张时才会退而求其次用更复杂的原地算法。我不建议在面试中把STL内部实现细节背一遍但你可以主动提一句“这道题本质上是稳定分区的特例把奇偶判断换成任意谓词就是通用稳定分区。”这一句话就能把刷题和系统知识串起来面试官会认为你对算法有体系性的理解而不是一个题一个题地死记。C标准库里的std::stable_partition、std::partition的差异适合作为延伸话题自己平时可以翻一翻源码。6. 我实测下来的一些细节与心得6.1 边界条件清单这道题看起来简单边界条件其实很多。我把自己实测时跑过的用例整理一下你可以直接拿去当自测清单测试输入期望输出说明[][]空数组任何解法都要直接返回[1][1]单元素无分区可做[2, 4, 6][2, 4, 6]全偶数不要误动[1, 3, 5][1, 3, 5]全奇数同样不要误动[2, 4, 1, 3, 5][1, 3, 5, 2, 4]标准混合用例[2, 1, 4, 3, 6, 5][1, 3, 5, 2, 4, 6]交替排列最容易写错[-3, 2, -1, 4][-3, -1, 2, 4]负数奇偶判断最后一个用例特别注意用x % 2 1的写法会输出[2, -1, -3, 4]直接错。我在LeetCode上提交过一次错误版本就是栽在这个负数用例上。另外一个容易忽略的点是交换类解法在大数组上要注意swap带来的缓存局部性问题双指针每交换一次就跳一大段内存cache miss比顺序遍历严重。笔试OJ数据规模小感受不出来但如果你在工程里实现百万级数组的稳定分区辅助数组顺序写的优势会更明显。6.2 白板代码的节奏面试遇到这题动手之前一定要先问清楚“请问调整之后需要保持奇数和偶数各自的相对顺序吗” 这个问题不是废话它是整道题最重要的决策分叉点。问一句得到“不需要”你再写双指针得到“需要保持”你再走稳定方案。很多候选人连需求都没有确认就直接闷头写代码写完才发现方向错了这在面试中是很大的失分项。白板上写代码之前我强烈建议先在心里或草稿纸上跑一遍[2, 4, 1, 3, 5]这个小例子。我自己的习惯是先画出两到三步的状态变化确认指针移动或位移的边界条件再落笔写完整函数。这样能避免至少一半的越界和逻辑错误。还有一个小技巧写完代码不要立刻说“写完了”而是再花十秒钟从头到尾读一遍自己的代码重点检查循环边界和空数组情况。这个习惯帮我挡掉了好几次现场改bug的尴尬。6.3 如果只能记一套把话说明白如果面试只允许你记住一套稳定解法毫不犹豫记辅助数组版本。它简单、正确、易解释复杂度好而且几乎不可能写错。原地右移版本作为“加餐”只有在面试官明确要求不使用额外空间时才拿出来。至于双指针它在整个答题流程里更像是“引言”先讲不稳定的最优解再分析为什么稳定性要求会推翻它然后引出两种稳定方案。这样一套组合下来面试官看到的不是你会背一道题而是你从问题出发做算法权衡的完整思路。反正我现在遇到数组分区这类题第一步永远是问条件第二步才是写代码。这道题给我最大的教训不是那个奇偶判断而是“看起来简单的题往往藏着一句附加条件”。多花十秒把题目和需求读清楚比多改半小时代码划算得多。
阅读完成 · 觉得有帮助？
