按符号重排数组 图解题解

这道题到底在问什么

输入

nums = [3,1,-2,-5,2,-4]

输出

[3,-2,1,-5,2,-4]

输入

nums = [-1,1]

输出

[1,-1]

先想最直接的笨办法

记牢这一句:正数排偶数位、负数排奇数位,i 和 j 各管一路、每次前进两格。下面从数组第一个元素开始,一个一个分派。（动画第 3 步）

最优解：一步一步想明白

1. 3记牢这一句:正数排偶数位、负数排奇数位,i 和 j 各管一路、每次前进两格。下面从数组第一个元素开始,一个一个分派。
2. 4开局先把结果数组 ans 摆出来,六个位置现在都空着,用小点表示。两个写指针也就位了:i 停在偶数位 0,准备接正数;j 停在奇数位 1,准备接负数。它们各走各的、互不干扰。下面从 nums 的第一个元素读起。
3. 5再把分工说清楚。ans 的偶数位 0、2、4 三个坑专留给正数,奇数位 1、3、5 三个坑专留给负数。因为下标 0 是偶数位,第一个填进去的正数就坐上了开头,正好满足以正数开头。正负各占一半坑,交替自然形成。
4. 6紫色指针移到 nums[0],读到的值是 3。分派之前只问一件事:它是正还是负。3 是正数,大于 0,该走偶数位这一路,交给指针 i。
5. 7把 nums[0] 标成绿色,提醒它是正数。正数这一路由 i 领着,i 现在指着偶数位 0,所以它的目标就是 ans[0]。右边面板用光束指向那个空槽。
6. 8把 3 落进 ans[0],这个坑就填实了。正数收完一个,i 加二跳到下一个偶数位 2,等着接下一个正数。 nums[0] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 1 个数。
7. 9紫色指针移到 nums[1],读到的值是 1。分派之前只问一件事:它是正还是负。1 是正数,大于 0,该走偶数位这一路,交给指针 i。
8. 10把 nums[1] 标成绿色,提醒它是正数。正数这一路由 i 领着,i 现在指着偶数位 2,所以它的目标就是 ans[2]。右边面板用光束指向那个空槽。
9. 11把 1 落进 ans[2],这个坑就填实了。正数收完一个,i 加二跳到下一个偶数位 4,等着接下一个正数。 nums[1] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 2 个数。
10. 12紫色指针移到 nums[2],读到的值是 -2。分派之前只问一件事:它是正还是负。-2 是负数,小于 0,该走奇数位这一路,交给指针 j。
11. 13把 nums[2] 标成红色,提醒它是负数。负数这一路由 j 领着,j 现在指着奇数位 1,所以它的目标就是 ans[1]。右边面板用光束指向那个空槽。
12. 14把 -2 落进 ans[1],这个坑就填实了。负数收完一个,j 加二跳到下一个奇数位 3,等着接下一个负数。 nums[2] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 3 个数。
13. 15紫色指针移到 nums[3],读到的值是 -5。分派之前只问一件事:它是正还是负。-5 是负数,小于 0,该走奇数位这一路,交给指针 j。
14. 16把 nums[3] 标成红色,提醒它是负数。负数这一路由 j 领着,j 现在指着奇数位 3,所以它的目标就是 ans[3]。右边面板用光束指向那个空槽。
15. 17把 -5 落进 ans[3],这个坑就填实了。负数收完一个,j 加二跳到下一个奇数位 5,等着接下一个负数。 nums[3] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 4 个数。
16. 18紫色指针移到 nums[4],读到的值是 2。分派之前只问一件事:它是正还是负。2 是正数,大于 0,该走偶数位这一路,交给指针 i。
17. 19把 nums[4] 标成绿色,提醒它是正数。正数这一路由 i 领着,i 现在指着偶数位 4,所以它的目标就是 ans[4]。右边面板用光束指向那个空槽。
18. 20把 2 落进 ans[4],这个坑就填实了。正数收完一个,i 加二跳到下一个偶数位 6,等着接下一个正数。 nums[4] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 5 个数。
19. 21紫色指针移到 nums[5],读到的值是 -4。分派之前只问一件事:它是正还是负。-4 是负数,小于 0,该走奇数位这一路,交给指针 j。
20. 22把 nums[5] 标成红色,提醒它是负数。负数这一路由 j 领着,j 现在指着奇数位 5,所以它的目标就是 ans[5]。右边面板用光束指向那个空槽。
21. 23把 -4 落进 ans[5],这个坑就填实了。负数收完一个,j 加二跳到下一个奇数位 7,等着接下一个负数。 nums[5] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 6 个数。
22. 24六个元素全部分派完毕。回头看一眼:偶数位 0、2、4 是 3、1、2,正是原来正数的先后;奇数位 1、3、5 是 -2、-5、-4,正是原来负数的先后。相邻两数一正一负交替,开头是正数,同号顺序原封不动。结果就是 [3,-2,1,-5,2,-4],和一开始记下的答案对上了。

⚠️ 容易写错的地方

完整代码（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 rearrangeArray(self, nums: List[int]) -> List[int]:
        ans = [0] * len(nums)
        i, j = 0, 1
        for x in nums:
            if x > 0:
                ans[i] = x
                i += 2
            else:
                ans[j] = x
                j += 2
        return ans

#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> rearrangeArray(vector<int>& nums) {
        vector<int> ans(nums.size());
        int i = 0, j = 1;
        for (int x : nums) {
            if (x > 0) {
                ans[i] = x;
                i += 2;
            } else {
                ans[j] = x;
                j += 2;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] rearrangeArray(int[] nums) {
        int[] ans = new int[nums.length];
        int i = 0, j = 1;
        for (int x : nums) {
            if (x > 0) {
                ans[i] = x;
                i += 2;
            } else {
                ans[j] = x;
                j += 2;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问