按奇偶排序数组 II 图解题解

偶数进偶数位、奇数进奇数位，要摆成什么样

给一个数组 nums，题目保证里面恰好一半偶数、一半奇数。要重新排一下，让每个偶数落在偶数下标、每个奇数落在奇数下标，任意一种合规摆法都算对。题面 nums=[4,2,5,7] 可以摆成 [4,5,2,7]：偶位 0、2 上是 4、2，奇位 1、3 上是 5、7。另一个例子 nums=[2,3] 本来就合规，原样返回就行。

开个等大的新数组分着填，卡在哪

另开一个和 nums 等大的新数组，扫一遍原数组，偶数往新数组的下一个偶位放、奇数往下一个奇位放，两个写指针各管一条，一趟 O(n) 就摆好了。麻烦在于它多吃了一个数组的 O(n) 空间，而这题进阶要求不开额外数组、原地摆好，只准用 O(1) 额外空间。所以真正要解决的是：能不能就在 nums 上挪，把奇偶各归各位。

不开新数组，怎么就地把奇偶各归各位

开两条下标轨道：一条只走偶下标 0、2、4…，用 i 标记；一条只走奇下标 1、3、5…，用 j 标记，两条各跳 2 步、互不串道。i 停在某个偶位，上面正好是偶数就本就对、跳过；上面是奇数就说明放错了。因为偶数奇数各占一半，偶位上多出一个奇数，必然有个奇位占着一个本该在偶位的偶数，它俩正是一对错位。让 j 沿奇位往后找到那个放错的偶数，和 i 这里一换，两处同时归位。

i、j 各跑各的轨道，一次交换修好两格

落到代码：i 用 for 循环从 0 起、每次 +2 扫遍偶位；j 从 1 起走奇位。i 每到一个偶位，先看那里是不是奇数，是偶数直接过。是奇数，就让 j 往后走，跳过奇位上那些本就是奇数、没放错的格子（每次 +2），直到停在一个偶数上，交换这两格。要紧的是 j 全程不重置：这一轮停在哪，下一轮从哪接着往后走，因为它走过的奇位要么已对位、要么已被换好，没必要回头。

题面 [4,2,5,7] 走一遍，只在偶位 2 换一次

数组长 4，奇位指针 j 从 1 起。先看偶位 0，上面是 4，偶数配偶位、本就对，跳过。再看偶位 2，上面是 5，奇数放错了，得去奇位找偶数换。此时 j 指向奇位 1，那里是 2，正好是偶数，j 不必再往后走，直接换：偶位 2 和奇位 1 交换，数组变成 [4,5,2,7]。偶位只剩这两个，循环结束，返回 [4,5,2,7]：偶位 4、2 全偶数，奇位 5、7 全奇数，各归各位。

j 每轮从 1 重扫，一趟就退化成两趟平方

先算账：i 从头到尾走偶位、j 从头到尾走奇位，两个都只增不减，合起来不过把数组扫一遍，时间 O(n)；全程在 nums 上原地交换，只多用 i、j 两个下标，空间 O(1)，进阶要求的不开额外数组也就满足了。

几处一改就错：i、j 若写成每次 +1 逐格走，就会落到不属于自己那半的下标上，两条轨道立刻串了。j 若每轮从 1 重扫，前面已对位的格子被反复检查，一趟 O(n) 拖成 O(n²)，接着上一轮往后走才对。交换对象也别找错：偶位放错时换的是奇位上放错的偶数，不是随手另一个奇数；至于 [2,3] 这种本就合规的，没有一个偶位是奇数，一次不换直接返回。

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 sortArrayByParityII(self, nums: List[int]) -> List[int]:
        n, j = len(nums), 1
        for i in range(0, n, 2):
            if nums[i] % 2:
                while nums[j] % 2:
                    j += 2
                nums[i], nums[j] = nums[j], nums[i]
        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> sortArrayByParityII(vector<int>& nums) {
        for (int i = 0, j = 1; i < nums.size(); i += 2) {
            if (nums[i] % 2) {
                while (nums[j] % 2) {
                    j += 2;
                }
                swap(nums[i], nums[j]);
            }
        }
        return nums;
    }
};

Java

import java.util.*;
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        for (int i = 0, j = 1; i < nums.length; i += 2) {
            if (nums[i] % 2 == 1) {
                while (nums[j] % 2 == 1) {
                    j += 2;
                }
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        return nums;
    }
}