企业官网建设流程全解析

1. 从一道简单题看排序思维的分水岭

LeetCode 905 这道题，标题叫“按奇偶排序数组”，难度标注是 Easy，但我带了这么多期算法训练营下来，发现一个很有意思的现象：同样一道题，有人三分钟写完提交，有人卡了半小时还在纠结指针怎么移动。差距不在语法，而在对“原地排序”和“辅助空间”这两条路线的理解深度上。

这道题的需求本身很朴素：给你一个整数数组，把所有偶数挪到前面，奇数挪到后面，不要求保持原有相对顺序，返回任意满足条件的数组即可。注意最后这半句——“任意顺序”，这是整道题的关键突破口，也是很多人第一眼会忽略的信息。如果题目要求保持偶数和奇数各自的相对顺序，那解法会完全不同，难度直接上一个台阶。但正因为没有这个约束，我们才能用双指针在 O(n) 时间、O(1) 空间内把它解决掉。

这篇文章我会从最直觉的暴力解法讲起，一路推到最优的原地双指针方案，把每一步的取舍逻辑讲透。适合刚刷到数组双指针章节的朋友，也适合已经能写出来、但想搞清楚“为什么这样写更稳”的读者。核心关键词就三个：原地排序、双指针、奇偶分区。搞懂这三个词在这道题里的具体含义，你后面遇到同类型的“分区”问题基本都能举一反三。

2. 题目拆解与三种解法路线对比

2.1 题目到底在考什么

先把题目翻译成人话。输入是一个乱序的整数数组，比如[3, 1, 2, 4]，你要输出一个数组，使得所有偶数值都在奇数值前面。[2, 4, 3, 1]是合法答案，[2, 4, 1, 3]也是合法答案，甚至[4, 2, 3, 1]同样合法。只要偶数全在前半段、奇数全在后半段，就算通过。

这里有个容易踩的认知坑：很多人下意识觉得“排序”就意味着要按大小排，于是去想快排、归并。但这道题的“排序”其实是分区（partition），只按奇偶这一个维度分成两组，组内顺序无所谓。理解这一点，你就不会往复杂排序算法上跑了。

另一个隐藏考点是原地。题目虽然没强制要求 O(1) 空间，但“原地排序”这个标签本身就是面试官想考察的方向。能不能在不额外开数组的前提下完成，是区分“会做题”和“懂算法”的分界线。

2.2 三条路线的取舍

我把常见解法归成三类，用一张表对比清楚：

新建数组的写法最省脑子：开一个等长结果数组，遍历原数组，偶数从头部塞进去，奇数从尾部塞回来。写起来五分钟，但空间翻倍，面试时如果面试官追问“能不能不用额外空间”，你就得现场改。

两次遍历的思路是：第一次从左往右找第一个奇数，第二次从右往左找第一个偶数，交换，循环。这个写法逻辑清晰，但指针来回扫，代码里嵌套循环容易写错边界。

首尾双指针是这道题的标准答案：左指针找奇数，右指针找偶数，找到就换，直到两指针相遇。一趟扫描搞定，代码短，效率高，是真正值得练到肌肉记忆的写法。

提示：面试里如果只写出新建数组的版本，大概率会被追问优化。建议直接把双指针版本练熟，一步到位。

3. 原地双指针的核心原理与手推过程

3.1 双指针为什么能成立

双指针能work，靠的是一个不变式：左指针左边的所有元素都是偶数，右指针右边的所有元素都是奇数。我们维护这个不变式，每次让左指针往右找“不该待在左边的奇数”，让右指针往左找“不该待在右边的偶数”，两者一交换，不变式继续成立，问题规模缩小。

用生活化的类比：一排人站队，要求女生站左边、男生站右边。你从左边开始走，遇到男生就停下；从右边开始走，遇到女生就停下；然后让这两个人换位置。换完之后，左边这段全是女生，右边这段全是男生，中间还没处理的部分继续用同样的方法处理。走到两人碰头，队伍就排好了。

这个类比里最关键的一点是：我们不需要关心换过来的那个人原来站在哪，因为交换本身就把两个“站错位置”的人同时纠正了。这就是双指针比单指针高效的原因——一次交换解决两个问题。

3.2 手推一遍完整过程

拿[3, 1, 2, 4]走一遍，把每一步的指针位置和数组状态都记下来：

初始状态：left = 0，right = 3，数组[3, 1, 2, 4]

第一步：left指向 3，是奇数，停下。right指向 4，是偶数，停下。交换nums[0]和nums[3]，数组变成[4, 1, 2, 3]。然后left++变 1，right--变 2。

第二步：left指向 1，是奇数，停下。right指向 2，是偶数，停下。交换nums[1]和nums[2]，数组变成[4, 2, 1, 3]。然后left++变 2，right--变 1。

第三步：left = 2，right = 1，left > right，循环结束。最终结果[4, 2, 1, 3]，偶数 4、2 在前，奇数 1、3 在后，符合要求。

再拿一个边界例子[2, 4, 6]（全是偶数）走一遍：left从 0 开始，指向 2 是偶数，left++；指向 4 是偶数，left++；指向 6 是偶数，left++变 3，此时left = 3 > right = 2，循环结束，数组原样返回。正确。

再看[1, 3, 5]（全是奇数）：left指向 1 是奇数，停下；right指向 5 是奇数，right--；指向 3 是奇数，right--；指向 1 是奇数，right--变 -1，left = 0 > right = -1，循环结束。数组原样返回，也正确。

3.3 循环条件为什么是 left < right

很多人写的时候会纠结用left < right还是left <= right。这里用left < right就够了，因为当left == right时，指向的是同一个元素，自己跟自己交换没有意义，而且此时中间只剩一个元素，它要么是偶数要么是奇数，无论哪种情况都已经满足“左边偶数、右边奇数”的不变式了，不需要再处理。

如果你写成left <= right，程序也不会错，只是多跑一次无意义的自交换。但在某些语言里，自交换如果涉及复杂对象可能有额外开销，所以养成写left < right的习惯更稳妥。

注意：内层两个 while 循环的条件里，left < right这个判断不能省。如果只写nums[left] % 2 == 1，当数组全是奇数时，left会一直往右冲，直接数组越界。这是这道题最高频的运行时错误，没有之一。

4. 代码实现与逐行注释

4.1 Python 版本

def sortArrayByParity(nums): left, right = 0, len(nums) - 1 while left < right: # 左指针找奇数 while left < right and nums[left] % 2 == 0: left += 1 # 右指针找偶数 while left < right and nums[right] % 2 == 1: right -= 1 # 交换 nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 return nums

逐行说一下。left, right = 0, len(nums) - 1初始化两个指针分别指向首尾。外层while left < right控制整体循环。第一个内层 while 让左指针跳过所有偶数，停在第一个奇数上；第二个内层 while 让右指针跳过所有奇数，停在第一个偶数上。两个内层循环都带了left < right保护，防止越界。交换之后，两个指针各走一步，继续下一轮。

有个细节值得说：交换后left += 1和right -= 1是必须的。因为交换后nums[left]已经是偶数、nums[right]已经是奇数，它们都处于正确位置，不需要再检查，直接跳过。如果不加这两行，程序会死循环。

4.2 Java 版本

public int[] sortArrayByParity(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { while (left < right && nums[left] % 2 == 0) { left++; } while (left < right && nums[right] % 2 == 1) { right--; } int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } return nums; }

Java 版本逻辑完全一致，只是交换用临时变量。注意 Java 里%对负数的处理：-3 % 2结果是-1，不是1。所以判断奇数时用nums[i] % 2 == 1对负数会失效。如果测试用例包含负数，应该写成nums[i] % 2 != 0来判断奇数，或者用(nums[i] & 1) == 1。这一点在 Python 里不存在，因为 Python 的-3 % 2结果是1，取模行为不同。

提示：LeetCode 905 的测试数据默认是非负整数，所以% 2 == 1没问题。但养成写% 2 != 0的习惯，迁移到其他题目时不会翻车。

4.3 复杂度分析

时间复杂度 O(n)：每个元素最多被访问一次，左右指针加起来总共走 n 步。空间复杂度 O(1)：只用了两个指针变量和一个临时变量，没有开新数组。这是这道题能达到的理论最优。

对比一下新建数组的 O(n) 空间版本，双指针版本在空间上省了一个数量级的开销。当数组规模到千万级别时，这个差距就是几百 MB 的内存，不是小事。

5. 常见错误与排查实录

5.1 越界崩溃：内层循环漏写边界保护

这是出现频率最高的错误。典型错误代码长这样：

while left < right: while nums[left] % 2 == 0: # 危险！没有 left < right 保护 left += 1 while nums[right] % 2 == 1: # 危险！ right -= 1 nums[left], nums[right] = nums[right], nums[left]

当数组是[2, 4, 6]时，第一个内层循环会让left一路加到 3，然后nums[3]直接越界报错。修复方法就是给每个内层循环都加上left < right条件。

5.2 死循环：交换后忘记移动指针

另一个高频错误是交换后不移动指针：

while left < right: while left < right and nums[left] % 2 == 0: left += 1 while left < right and nums[right] % 2 == 1: right -= 1 nums[left], nums[right] = nums[right], nums[left] # 忘记 left += 1 和 right -= 1

这样写，交换后nums[left]变成偶数、nums[right]变成奇数，下一轮循环两个内层 while 会立刻跳过它们，但指针位置没变，又回到同样的位置交换，无限循环。加上left += 1和right -= 1即可。

5.3 负数取模判断错误

前面提过，Java、C++ 里负数取模结果可能是负数。-3 % 2 == -1，用== 1判断奇数会漏掉负数。统一用!= 0判断奇数最安全。

5.4 常见问题速查表

注意：调试这类双指针题，最有效的方法是把指针位置和数组状态打印出来，手动对照不变式。别靠脑补，脑补十次有八次是错的。

6. 从这道题延伸出去的分区思维

6.1 同类型题目的迁移

905 的本质是“二分区”，把数组按某个条件分成两组。这个模式可以迁移到很多题：

• 颜色分类（荷兰国旗问题）：把数组分成三组（0、1、2），用三指针，是二分区的升级版。
• 移动零：把所有 0 移到末尾，保持非零元素相对顺序，用快慢指针。
• 数组划分：按给定阈值划分，小于阈值的放左边，大于等于的放右边。

这些题的共同点是：分区条件明确、组内顺序无要求。一旦题目加上“保持相对顺序”的约束，双指针交换法就不适用了，得换成稳定分区算法，通常需要额外空间或更复杂的移动逻辑。

6.2 面试中的追问方向

面试官出完 905，常见的追问有三个层次：

第一层：“能不能不用额外空间？”——考察你知不知道双指针。

第二层：“如果要求偶数和奇数各自的相对顺序不变呢？”——这时候双指针交换法会打乱顺序，需要换思路。一种做法是新建数组分别收集偶数和奇数再拼接，空间 O(n)；另一种是原地做类似插入排序的移动，时间退化到 O(n²)。

第三层：“如果数组里有三种类型的元素呢？”——直接引出荷兰国旗问题，考察三指针的掌握。

把这三个层次都想清楚，这道 Easy 题就能榨出 Medium 的价值。

6.3 我个人的练习建议

我带训练营时，要求学员对 905 做到“三遍成型”：第一遍照着题解写，理解双指针不变式；第二遍关掉题解默写，重点检查边界条件；第三遍改条件——把“偶数在前”改成“奇数在前”，把“非负”改成“含负数”，看代码是否还正确。

第三遍最有用，因为它逼你思考每一行代码的适用边界，而不是背模板。很多人刷题量大但遇到变体就懵，就是因为只背了代码没理解不变式。双指针的不变式一旦吃透，这类分区题基本就是送分题。

最后分享一个我自己的调试习惯：写完双指针代码，先拿三个用例手动跑——全偶数、全奇数、一偶一奇。这三个覆盖了所有边界，跑通基本就不会有越界和死循环问题。这个习惯帮我省了无数次提交失败的等待时间。