LeetCode 905简单双指针 · 滑窗
按奇偶排序数组 图解题解
这道题到底在问什么
给定整数数组 nums，重新排列，使得所有偶数都排在所有奇数前面。返回满足条件的任一数组。偶数之间、奇数之间的相对顺序不作要求。
- 输入
- nums=[3,1,2,4]
- 输出
- [4,2,1,3] （[2,4,3,1] 等也算对，只要偶在前奇在后）
- 输入
- nums=[0]
- 输出
- [0] （单个元素直接返回）
最优解：一步一步想明白
- 3记住这套「左偶就 i++、右奇就 j--、左奇右偶就交换」，下面每一帧都在套它。
- 4双指针就位：i（左指针）站在下标 0，j（右指针）站在下标 7。中间紫色窗口是还没分好的区域。我们要让窗口里的偶数都流到左边、奇数都流到右边。
- 5先看左指针。nums[0] = 3 是奇数，奇数该去右边，这一位站错了，先记着它，再去看右指针。
- 6再看右指针。nums[7] = 7 也是奇数，而奇数本来就该待在右边，这一位其实是站对的。
- 7左边奇数虽然站错，但右边是个已经站对的奇数，没法跟它换。所以先把右指针 j 往左收一格，把这个奇数定下来。
- 8j 退到下标 6。下标 7 的 7 归入右边的奇数区（蓝色）。左指针那个奇数下一轮再处理。
- 9先看左指针。nums[0] = 3 是奇数，按规矩它该去右边，是个站错位的。
- 10再看右指针。nums[6] = 8 是偶数，按规矩它该来左边，也是个站错位的。两个刚好反着。
- 11这是最划算的一步：左边的奇数和右边的偶数一交换，两个就都各就各位了。准备交换。
- 12换完：下标 0 变成偶数 8，下标 6 变成奇数 3，都站对了。于是 i 右移到 1、j 左移到 5，窗口同时缩小两头。
- 13先看左指针。nums[1] = 2 是偶数，偶数本来就该待在左边，这一位已经站对了。
- 14既然左指针指的是偶数、位置正确，就不用动它，直接让 i 往右迈一步，去检查下一个。
- 15i 走到下标 2。下标 1 的 2 正式归入左边的偶数区（绿色）。继续看新的左指针。
- 16先看左指针。nums[2] = 1 是奇数，奇数该去右边，这一位站错了，先记着它，再去看右指针。
- 17再看右指针。nums[5] = 5 也是奇数，而奇数本来就该待在右边，这一位其实是站对的。
- 18左边奇数虽然站错，但右边是个已经站对的奇数，没法跟它换。所以先把右指针 j 往左收一格，把这个奇数定下来。
- 19j 退到下标 4。下标 5 的 5 归入右边的奇数区（蓝色）。左指针那个奇数下一轮再处理。
- 20先看左指针。nums[2] = 1 是奇数，按规矩它该去右边，是个站错位的。
- 21再看右指针。nums[4] = 6 是偶数，按规矩它该来左边，也是个站错位的。两个刚好反着。
- 22这是最划算的一步：左边的奇数和右边的偶数一交换，两个就都各就各位了。准备交换。
- 23换完：下标 2 变成偶数 6，下标 4 变成奇数 1，都站对了。于是 i 右移到 3、j 左移到 3，窗口同时缩小两头。
- 24两个指针在下标 3 撞上了，中间再没有未处理的元素，循环停止。此刻左边四个全是偶数、右边四个全是奇数。
- 25分区完成：绿色 8、2、6、4 都是偶数，蓝色 1、5、3、7 都是奇数。偶在前、奇在后，这就是一个合法答案。
⚠️ 容易写错的地方
✗ 错：用「新建偶数表 + 奇数表再拼接」
✓ 对：双指针原地交换
题目允许任意顺序，原地两指针更省空间，O(1)
✗ 错：循环条件写成 i ≤ j
✓ 对：应为 i 比 j 小
i 等于 j 时指向同一个元素，无需再处理，写 ≤ 会多绕一步
✗ 错：右边是奇数时还去交换
✓ 对：右奇数已站对，只需 j 左移
盲目交换会把已归位的奇数又换走，破坏分区
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
i, j = 0, len(nums) - 1
while i < j:
if nums[i] % 2 == 0:
i += 1
elif nums[j] % 2 == 1:
j -= 1
else:
nums[i], nums[j] = nums[j], nums[i]
i, j = i + 1, j - 1
return numsC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
int i = 0, j = nums.size() - 1;
while (i < j) {
if (nums[i] % 2 == 0) {
++i;
} else if (nums[j] % 2 == 1) {
--j;
} else {
swap(nums[i++], nums[j--]);
}
}
return nums;
}
};Java
import java.util.*;
class Solution {
public int[] sortArrayByParity(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 == 0) {
++i;
} else if (nums[j] % 2 == 1) {
--j;
} else {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
++i;
--j;
}
}
return nums;
}
}复杂度
时间
O(n)
i 与 j 合起来只把数组扫过一遍
空间
O(1)
原地交换，只用 i、j 两个下标
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 按奇偶排序数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和「快速排序的分区（partition）」有什么关系？+
本质一样，都是把数组按某个判定分成两段。这里的判定是「奇偶」而不是「与基准比大小」，双指针相向夹逼、遇到两边都不满足就交换，正是 partition 的标准套路。理解了这题，再看快排的 partition 会很顺。
如果还要求偶数之间保持原有相对顺序（稳定）怎么办？+
本题不要求稳定，所以可以原地交换。若要稳定，原地交换会打乱顺序，得改用「额外数组按顺序先放偶数再放奇数」的两次扫描，空间变 O(n)，换取稳定性。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 按奇偶排序数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。