LeetCode 922. 按奇偶排序数组 II
目录
题目描述
题意分析
给一个长度为偶数的数组，其中恰好一半是偶数、一半是奇数。要求重排它，使得每个偶数下标上放的是偶数、每个奇数下标上放的是奇数。任何满足条件的排列都算正确答案。
有三个约束信号值得单独拎出来。第一，「奇偶各占一半」是题目给的硬保证，不是需要验证的条件，这意味着不存在无解情况，代码里不必写失败分支。第二，题目明说答案不唯一，所以完全不需要考虑元素间的相对顺序，也谈不上真正意义上的排序。第三，值域是非负整数，取模判断奇偶不会遇到负数取模的符号问题。
再看目标本身：这里唯一被约束的是「下标的奇偶性」与「元素的奇偶性」要对上，元素的大小关系毫无作用。想清楚这一点，题目就从「排序」退化成了「分类归位」。
边界上，数组长度至少为
2，所以不会出现空数组；长度必为偶数，因此最后一个下标一定是奇数下标，两类位置的数量严格相等。
解法：奇偶下标分流填充
核心思路
一个自然但走偏的想法是排序：把偶数全排前面、奇数全排后面，再想办法交错。这既做了多余的工作（题目不关心顺序），又没有直接解决交错问题，反而更绕。瓶颈在于把「归位」误当成了「定序」。
退回到问题本身：每个元素只有两种身份（奇或偶），每个位置也只有两种身份（奇下标或偶下标），而且两边的数量恰好一一匹配。这是一个纯粹的分配问题——把每个元素投递到对应类型的下一个空位即可，谁先谁后完全无所谓。
于是开一个等长的结果数组，用两个写指针分别管理两类空位：
evenIdx指向下一个待填的偶数下标，从0起步；oddIdx指向下一个待填的奇数下标，从1起步。每写一个就把对应指针加2，自然跳到同类的下一个位置。不变量是：任意时刻，
evenIdx恒为偶数且res中所有小于evenIdx的偶数下标都已填入偶数；oddIdx恒为奇数且res中所有小于oddIdx的奇数下标都已填入奇数。 两个指针步长都是2，起点奇偶性不同，所以它们的取值集合永不相交，写入互不覆盖。由于奇偶元素各占一半，遍历结束时两个指针恰好都越过数组末尾，所有位置被填满且无一重复。
解题步骤
- 新建与
nums等长的结果数组res。用新数组而不是就地交换，是为了让每个元素的落位一次确定，不需要处理「换过去的那个又该放哪」的连锁问题。- 初始化
evenIdx = 0、oddIdx = 1。起点必须分别取最小的偶数下标和最小的奇数下标，这样加2的步进才能覆盖各自的全部位置。- 顺序遍历
nums中的每个num，只判断它自身的奇偶性，不看它原来在哪个下标。原下标信息在本题里没有任何价值。- 若
num % 2 == 0，写入res[evenIdx]并令evenIdx += 2；否则写入res[oddIdx]并令oddIdx += 2。写入与推进必须成对出现，漏掉推进会导致同一个位置被反复覆盖。- 全部遍历完直接返回
res。因为题目保证了数量匹配，不需要任何越界检查或补漏逻辑。以
nums = [4,2,5,7]走一遍：初始res = [_,_,_,_]、evenIdx = 0、oddIdx = 1。第一个元素4是偶数，写入res[0]，res变成[4,_,_,_]，evenIdx推进到2。第二个元素2是偶数，写入res[2]，res变成[4,_,2,_]，evenIdx推进到4（已越界，但之后不会再有偶数，永远不会被使用）。第三个元素5是奇数，写入res[1]，res变成[4,5,2,_]，oddIdx推进到3。第四个元素7是奇数，写入res[3]，res变成[4,5,2,7]，oddIdx推进到5。返回[4,5,2,7]：下标0和2上是偶数4、2，下标1和3上是奇数5、7，完全符合要求。再以nums = [3,1,4,2]走一遍：3是奇数写res[1]，1是奇数写res[3]，4是偶数写res[0]，2是偶数写res[2]，最终res = [4,3,2,1]，同样合法。
代码实现
class Solution {
public int[] sortArrayByParityII(int[] nums) {
int[] res = new int[nums.length];
int evenIdx = 0;
int oddIdx = 1;
// 偶数只写偶数位，奇数只写奇数位，两个指针互不干扰。
for (int num : nums) {
if (num % 2 == 0) {
res[evenIdx] = num;
evenIdx += 2;
} else {
res[oddIdx] = num;
oddIdx += 2;
}
}
return res;
}
}
func sortArrayByParityII(nums []int) []int {
res := make([]int, len(nums))
evenIdx := 0
oddIdx := 1
// 偶数只写偶数位，奇数只写奇数位，两个指针互不干扰。
for _, num := range nums {
if num%2 == 0 {
res[evenIdx] = num
evenIdx += 2
} else {
res[oddIdx] = num
oddIdx += 2
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是数组长度。只做一趟遍历，每个元素上的工作是一次取模、一次写入、一次加法，都是常数时间。
- 空间复杂度：$O(n)$，额外开了一个等长的结果数组；除此之外只有两个整型指针。若把返回数组算作必要输出，则额外开销为 $O(1)$。
关键点总结
- 先分清题目要的是「定序」还是「归位」。本题只约束奇偶匹配、不约束相对顺序，识破这点就能直接跳过排序，把复杂度从 $O(n \log n)$ 降到 $O(n)$。
- 两类目标位置各配一个步长为
2的写指针，是处理「交错填充」的通用模板。起点取不同奇偶、步长相同，就能保证两条写入轨道天然不冲突。- 题目给出的数量保证要主动利用。既然奇偶各占一半，就不必写越界保护和无解分支，代码更短也更不容易错。
- 面试视角：这题的进阶要求是常数额外空间。要能说出就地双指针的做法：
i走偶数下标、j走奇数下标，各自跳过已经匹配的位置，一旦同时发现nums[i]是奇数且nums[j]是偶数就交换两者；由于数量匹配，两个指针会同步耗尽。- 面试视角：被问「为什么就地版本一定能配上对」时，答案是计数论证——偶数下标上多出来的奇数个数，必然等于奇数下标上多出来的偶数个数，所以每次都能凑成一对交换。能讲清这句话比写出代码更有说服力。
易错点总结
- 错误写法：
oddIdx初始化为0或与evenIdx同起点。用例[4,2,5,7]→ 奇数被写到偶数下标上，res[0]先被4填再被5覆盖，结果既有覆盖又有空位。- 错误写法：写入后指针加
1而不是加2。用例[4,2,5,7]→evenIdx依次取0、1，把偶数2写进了奇数下标1，奇偶匹配被破坏。- 错误写法：写入后忘记推进指针。用例
[4,2,5,7]→ 两个偶数都写进res[0]，4被2覆盖，res[2]保持默认值0，输出错误。- 错误写法：按下标的奇偶性去分类元素，即写成
if (i % 2 == 0)来决定往哪写。用例[4,2,5,7]→ 分类依据用错了对象，原下标与元素奇偶无关，结果等于原样拷贝。- 错误写法：先对数组整体排序，再把前一半填进偶数下标、后一半填进奇数下标。用例
[2,3,4,5]→ 排序后仍是[2,3,4,5]，前一半2、3分别落到下标0和2，奇数3被放进了偶数下标，判定失败；这种做法既不成立又白付了 $O(n \log n)$。- 错误写法：就地交换版本里只推进其中一个指针。用例
[4,2,5,7]→ 交换后没有同时推进两个游标，会重复检查同一对位置，轻则死循环，重则把已经归位的元素换回去。- 错误写法：用
num & 1 == 0判断偶数但忘了运算符优先级，在 Java 中写成if (num & 1 == 0)。用例任意输入 →==优先级高于&，表达式类型不匹配直接编译失败。- 错误写法：直接返回
nums而不是res。用例[4,2,5,7]→ 原数组未被修改，返回的仍是不满足条件的原序列。- 错误写法：把这套写法迁移到可能含负数的变体时仍用
num % 2 == 0之外的写法，例如num % 2 == 1判奇数。本题值域非负不受影响，但在负数输入下-3 % 2在 Java 和 Go 中都等于-1，判定失败，所有负奇数会被归入偶数分支。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 905. 按奇偶排序数组 | 简单 | 只要求偶数在前奇数在后，用对撞双指针即可 |
| 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 | 简单 | 与上题镜像，考察就地划分的写法熟练度 |
| 283. 移动零 | 简单 | 需保持非零元素相对顺序，用快慢指针覆盖式前移 |
| 75. 颜色分类 | 中等 | 三类元素的一趟原地划分，需要三指针协同 |
| 328. 奇偶链表 | 中等 | 按位置奇偶拆链表，考察指针重接而非数值判定 |
| 86. 分隔链表 | 中等 | 按阈值把链表分成两段并保序，最后首尾相接 |