按奇偶排序数组 图解题解

把偶数全挪到奇数前面，要返回什么才算数

给一个整数数组 nums，重排它，让所有偶数排在所有奇数前面，返回满足条件的任一数组即可；偶数、奇数各自谁先谁后都不管。题面 nums=[3,1,2,4]，输出 [4,2,1,3]，其实 [2,4,3,1] 也算对，只要偶在前奇在后。再看 nums=[0]，单个元素直接返回 [0]。「任一」是重点：不排序、也不强求稳定。

先分两个表再拼起来，差在哪儿

扫一遍 nums，偶数进一个表、奇数进另一个表，最后两表拼回去，答案就有了。逻辑没错，时间也是 O(n)，可这一路白开了两个和 nums 一样长的表，多花 O(n) 额外空间。题目只要偶在前奇在后、不追究具体顺序，这份空间能省掉。

凭什么两个指针相向走一趟就能分好

既然允许任意顺序，就不必搬新表，直接在原数组上把偶数拨到左、奇数拨到右。摆两个指针：i 从最左、j 从最右，相向往中间走。i 只要停在偶数上就往右迈、j 只要指着奇数就往左退；只有 i 指奇数、j 指偶数、两边都站错时才交换，双双归位后再各进一步。一头一尾对着夹，中间没分好的窗口越缩越小，碰上就分完。在原数组上按一个判定拆成两段，就是对撞双指针原地分区。

左指针右指针，各自碰到什么才动

每一轮先看 i：nums[i] 是偶数（nums[i] % 2 == 0）就站对，i 右移；不是偶数，再看 j，nums[j] 是奇数（nums[j] % 2 == 1）也站对，j 左移；两条都不满足，只剩 i 指奇数、j 指偶数这一种，交换 nums[i] 与 nums[j]，随后 i 右移、j 左移。循环条件是 i 比 j 小，等两者相遇或错开就停下返回 nums。判断先后有讲究：先放过站对的偶数、再退走站对的奇数，剩下的才是「左奇右偶」那种一换解决俩的情形；右边站对的奇数别硬换，否则会把归位的奇数又拖回窗口。

[3,1,2,4] 分两步落位，一步一步看

起手 i 指向下标 0、j 指向下标 3。nums[0]=3 奇数，i 不动；nums[3]=4 偶数、非奇数，j 也不退；落到交换，nums[0] 和 nums[3] 对调，数组变成 [4,1,2,3]，i 到下标 1、j 到下标 2。第二轮 nums[1]=1 奇、nums[2]=2 偶，又交换，nums[1] 和 nums[2] 对调，数组成 [4,2,1,3]，i 到下标 2、j 到下标 1。这时 i 比 j 大，循环停，返回 [4,2,1,3]——偶数 4、2 在前，奇数 1、3 在后，偶在前奇在后就对了。

循环条件用 i 小于等于 j，会白空转一轮

i 和 j 合起来只把数组从两头扫过一遍，时间 O(n)；全程只多用 i、j 两个下标、就地交换，空间 O(1)。几种边界都不触发交换、原样返回就对：单元素如 nums=[0]，i 和 j 起手同位，条件 i 比 j 小不成立，一轮不进直接返回；全是偶数则 i 右移到头、全是奇数则 j 左移到头，都不交换。收尾一个爱写错的点：循环写成 i 小于等于 j，等 i、j 落到同一元素上还会多进一轮，对已定的位置空转，改成 i 比 j 小才干净。

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 nums

C++

#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;
    }
}