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

这道题到底在问什么

输入

nums=[4,2,5,7]

输出

[4,5,2,7] （偶位放偶数、奇位放奇数）

输入

nums=[2,3]

输出

[2,3] （本来就合规，原样返回）

最优解：一步一步想明白

1. 3记住这套「偶位放偶数、奇位放奇数，i 和 j 各跳 2」，下面每一帧都在套它。
2. 4先看规则:下标是偶数的格子要放偶数，下标是奇数的格子要放奇数。现在这个数组还没摆好。
3. 5放两个指针:偶位指针标 i 从 0 起，奇位指针标 r(就是代码里的 j)从 1 起。i 只落偶数下标、j 只落奇数下标，各跳 2 步。
4. 6红色这 4 个都放错了:偶位 0 和 2 上是奇数 3、5，奇位 1 和 5 上是偶数 4、2。它们正好两两配对，一次交换能同时修好两处。
5. 7i 跳到偶位 0，看看上面是什么:这里是 3。
6. 83 是奇数，却站在偶位 0，放错了(变红)。要去奇位那边找一个放错的偶数来跟它换。
7. 9j 到奇位 1，这里是 4，偶数却站在奇位，正是放错的，就用它跟偶位 0 交换。
8. 10交换:偶位 0 拿到偶数 4，奇位 1 拿到奇数 3，两边同时归位(变绿)。
9. 11i 跳到偶位 2，看看上面是什么:这里是 5。
10. 125 是奇数，却站在偶位 2，放错了(变红)。要去奇位那边找一个放错的偶数来跟它换。
11. 13j 在奇位 1，这里是 3，奇数待在奇位是对的，不能动，j 加 2 接着往后找。
12. 14j 在奇位 3，这里是 7，奇数待在奇位是对的，不能动，j 加 2 接着往后找。
13. 15j 到奇位 5，这里是 2，偶数却站在奇位，正是放错的，就用它跟偶位 2 交换。
14. 16交换:偶位 2 拿到偶数 2，奇位 5 拿到奇数 5，两边同时归位(变绿)。
15. 17i 跳到偶位 4，看看上面是什么:这里是 6。
16. 186 是偶数，正好站在偶位 4，本来就对(变绿)，跳过，i 接着往后走。
17. 19i 跳到偶位 6，看看上面是什么:这里是 8。
18. 208 是偶数，正好站在偶位 6，本来就对(变绿)，跳过，i 接着往后走。
19. 21i 把偶位 0、2、4、6 都看过了，循环结束。下面逐位验收一下结果。
20. 22先看偶位:0、2、4、6 上分别是 4、2、6、8，全是偶数，符合要求。
21. 23再看奇位:1、3、5、7 上分别是 3、7、5、1，全是奇数，也符合要求。
22. 24整个数组摆好了:偶位放偶数、奇位放奇数。答案就是 [4,3,2,7,6,5,8,1]。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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

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

复杂度

面试官可能追问