LeetCode 905. 按奇偶排序数组
目录
题目描述
题意分析
给定一个非负整数数组，要求重排成「所有偶数在前、所有奇数在后」的形式并返回。
题面里最重要的一句是「满足条件的答案不唯一，返回任意一个即可」。这句话解除了保持相对顺序的约束——只要求偶奇两段分开，段内谁先谁后完全自由。这直接决定了可以用交换而不必用搬移。
题目说的「排序」只是借用了词，实际要的是二值分区：判据只有
x % 2一个比特，不涉及任何大小比较。识别出这一点，就不该往sort或比较器的方向走。边界情况：数组全是偶数；全是奇数；只有一个元素；数组含 0（0 是偶数，容易在写
% 2 == 1时想歪）。
解法：双指针原地分区
核心思路
题目只要求偶数全部位于奇数之前，不要求两组内部有序，也不要求保持原相对顺序。因此这是二值分区问题，不需要真正排序；可以直接交换两端放错位置的元素，把额外空间降到 $O(1)$。
用
left、right维护不变量：
[0, left)全是偶数。(right, n - 1]全是奇数。[left, right]尚未确定。
left跳过已经正确的偶数，right跳过已经正确的奇数。两者停下时，左边是错位奇数、右边是错位偶数，交换一次能同时修正两个位置。随后两指针收缩，直到待处理区间为空。每一步都只扩大已经正确的两侧区间，所以不变量保持成立；循环结束时两侧覆盖整个数组，必然满足所有偶数在所有奇数之前。
解题步骤
- 初始化
left = 0、right = n - 1。- 当左端是偶数时右移
left。- 当右端是奇数时左移
right。- 若
left < right，交换两个错位元素并同时收缩指针。- 指针相遇或交错后返回原数组。
对
[3,1,2,4]，先交换 3 和 4 得[4,1,2,3]，再交换 1 和 2 得[4,2,1,3]。组内顺序改变不影响题目要求。
代码实现
class Solution {
public int[] sortArrayByParity(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
while (left < right && nums[left] % 2 == 0) {
left++;
}
while (left < right && nums[right] % 2 != 0) {
right--;
}
if (left < right) {
int value = nums[left];
nums[left] = nums[right];
nums[right] = value;
left++;
right--;
}
}
return nums;
}
}
func sortArrayByParity(nums []int) []int {
left, right := 0, len(nums)-1
for left < right {
for left < right && nums[left]%2 == 0 {
left++
}
for left < right && nums[right]%2 != 0 {
right--
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
return nums
}
复杂度分析
- 时间复杂度：$O(n)$。两个指针都单向移动，总移动次数不超过线性数量级。
- 空间复杂度：$O(1)$，只在原数组内交换。
关键点总结
- “答案不唯一”意味着无需稳定分区，交换法才是合法的。
- 两侧已确定区间的不变量决定了指针移动和循环边界。
- 这就是快速排序 partition 的二分类版本。
- 若追问稳定分区，允许 $O(n)$ 空间时可两趟收集；本解法不保持相对顺序。
易错点总结
- 内层循环不带
left < right边界，全偶或全奇数组会越界。- 外层使用
left <= right却不处理相等情形，单元素时可能死循环。- 指针交错后仍交换，会破坏已经正确的分区。
- 把题意当成数值排序，使用 $O(n \log n)$ 排序既多做工作也偏离考点。
- 忘记 0 是偶数；判断奇数时写
% 2 != 0也能兼容负数变体。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 922. 按奇偶排序数组 II | 简单 | 奇偶下标与奇偶值一一对应 |
| 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 | 简单 | 奇数在前的反向分区 |
| 75. 颜色分类 | 中等 | 三路分区与荷兰国旗 |
| 283. 移动零 | 简单 | 保持相对顺序的原地搬移 |