LeetCode 922. 按奇偶排序数组 II
题目描述
题意分析
重新排列数组，使偶数下标存放偶数，奇数下标存放奇数。题目保证数组长度为偶数，且一半元素是偶数、一半是奇数，因此总能填满两类位置。符合条件的结果不唯一，不要求按数值大小排序。
可以新建结果数组，把两类值分别填入对应下标；题目进阶还要求不使用额外空间，需要在原数组中找到放错的奇数和偶数，并通过交换同时修正两个位置。
解法：奇偶下标分流填充
核心思路
[!blue]
创建与输入等长的结果数组。偶数下标共有
n / 2个，用evenIdx = 0管理下一个可写位置；奇数下标也有n / 2个，用oddIdx = 1管理。两个指针每次增加2，便始终留在各自的下标集合中。遍历每个输入值，只根据它本身的奇偶性决定写入哪个位置，不看它原来位于哪里。写入后推进对应指针，另一个指针不动。已经写入的位置不再重复使用，两类指针也不会互相覆盖。
题目保证两类元素的数量恰好等于两类位置的数量，所以每个值都有可写位置，结束时又恰好填满结果。此方法保留同类值的原相对顺序，但这只是顺序扫描带来的效果，并非题目要求。
解题步骤
- 分配等长结果数组，初始化偶数写指针为
0、奇数写指针为1。- 顺序读取输入值，偶数写入偶数指针位置，奇数写入奇数指针位置。
- 每次只把实际使用的那个写指针增加
2。- 返回结果数组，原数组不变。
代码实现
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)$。
- 空间复杂度：结果 $O(n)$，其余辅助空间 $O(1)$。
关键点总结
[!green]
- 分类依据数字的奇偶，不是它原来的下标。
- 两种位置分别推进，不能共用连续写指针。
- 结果单独分配，输入数组保持不变；符合条件的排列不唯一。
解法二：双指针交换错位元素
核心思路
[!blue]
额外数组可以省掉：偶数位置如果放了奇数，就一定有某个奇数位置放着偶数。因为两类位置和两类值数量相等，放错到偶数位置的奇数个数，恰好等于放错到奇数位置的偶数个数。把这两个错位值交换，两个位置都会同时变正确。
用
even依次检查偶数下标，位置上已经是偶数就跳过；发现奇数时，用odd从尚未检查的奇数下标向后寻找偶数。奇数位置上原本正确的奇数直接跳过，找到偶数后与当前错位值交换。两个指针都每次前进
2，已经正确的位置不再改动。只要当前偶数位置仍错放着奇数，就必然还存在一个错放偶数的奇数位置，因此在题目数量保证下，查找不会越界。交换完成后继续向后，最终所有位置都满足要求。
解题步骤
- 初始化
odd = 1，让even从0开始每次增加2。- 偶数位置已经放着偶数时，继续检查下一个偶数位置。
- 否则让
odd每次增加2，跳过其中正确的奇数，直到找到偶数。- 交换这两个错位值，再让
odd增加2，继续处理后续位置。- 返回已经原地重排的
nums。
代码实现
class Solution {
public int[] sortArrayByParityII(int[] nums) {
int odd = 1;
for (int even = 0; even < nums.length; even += 2) {
if (nums[even] % 2 == 0) {
continue;
}
while (nums[odd] % 2 != 0) {
odd += 2;
}
int temp = nums[even];
nums[even] = nums[odd];
nums[odd] = temp;
odd += 2;
}
return nums;
}
}
func sortArrayByParityII(nums []int) []int {
odd := 1
for even := 0; even < len(nums); even += 2 {
if nums[even]%2 == 0 {
continue
}
for nums[odd]%2 != 0 {
odd += 2
}
nums[even], nums[odd] = nums[odd], nums[even]
odd += 2
}
return nums
}
复杂度分析
- 时间复杂度：$O(n)$，两个指针只向后移动，各检查至多一半下标。
- 空间复杂度：$O(1)$，只使用两个下标与交换临时变量，直接修改原数组。
关键点总结
[!green]
- 交换两处错误：一个位置错放奇数、另一个错放偶数，交换后双方同时满足要求。
- 数量条件保证配对存在：不能把这个实现直接用于奇偶元素数量不符合题意的输入。
- 步长固定为二：每个指针只管理自己所属的下标集合，已经修正的位置不再处理。
易错点总结
[!yellow]
- 写后只加一会进入另一类下标。
- 奇数指针也从零开始，会覆盖偶数位置。
- 按原下标分类，会把原来放错的位置继续保留。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 905. 按奇偶排序数组 | 简单 | 本题需要把奇数送到奇数下标、偶数送到偶数下标，不是简单地分成前后两段。 |