LeetCode 905. 按奇偶排序数组
题目描述
题意分析
调整数组，使所有偶数都出现在所有奇数之前，返回任意满足条件的排列即可。两组内部不要求按大小排序，也不要求保留原相对顺序，因此可以直接在原数组中交换。0 属于偶数。
解法：双指针原地分区
核心思路
[!blue]
用
left、right从两端向中间处理。始终保持：left左侧全是偶数，right右侧全是奇数；闭区间[left, right]尚未确定。左端遇到偶数，已经符合前半部分的要求，可以右移
left；右端遇到奇数，可以左移right。两次扫描后若仍有left < right，左端必为奇数，右端必为偶数，交换即可同时放对两个元素，再把两个指针各收缩一步。每次移动都只扩大已经正确的两段。指针交错时没有待处理元素；相遇时只剩一个元素，它无论是偶数还是奇数，位于“全偶数段”和“全奇数段”之间都符合要求。所以循环条件是
left < right，不必再处理相遇位置。
解题步骤
- 初始化
left = 0、right = n - 1。- 在
left < right的前提下，让左指针跳过偶数，右指针跳过奇数。- 若此时仍有
left < right，交换两端错位元素，再执行left++、right--。- 重复扫描和交换，直到两个指针相遇或交错，返回原数组。
每轮要么扫描推进了指针，要么通过交换同时收缩两端，待处理区间不断缩小，因此不会停在同一对位置上。
代码实现
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)$，只在原数组内交换。
关键点总结
[!green]
- 题目只要求按奇偶分组，允许交换，不需要排序或维护组内相对顺序。
- 左侧已确认全偶、右侧已确认全奇，扫描和交换始终维持这两个条件。
- 指针相遇时最后一个元素自然处在两组交界处，无需额外判断。
易错点总结
[!yellow]
- 两个内层循环也必须检查
left < right，否则全偶数或全奇数时可能越界。- 扫描后应再次检查
left < right，确认两端仍是两个需要交换的位置。- 偶数条件是余数为 0，包含数值 0；不能将 0 漏掉。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 922. 按奇偶排序数组 II | 简单 | 本题只把偶数放前奇数放后，原题要求每个下标的奇偶性与元素一致，分配位置规则不同。 |
| 283. 移动零 | 简单 | 同样按条件分组，本题通常不要求稳定顺序，移动零要保留非零元素相对次序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！