按符号重排数组 图解题解

重排后要正负交替、正数开头，还得保住同号先后

给一个长度为偶数的数组 nums，正数和负数一样多。要把它重排成任意相邻两数一正一负交替、并以正数打头；同时同为正（或同为负）的那些数，彼此的先后顺序要和原数组一模一样。题面例子 nums=[3,1,-2,-5,2,-4]，正数按出场是 3、1、2，负数是 -2、-5、-4，唯一答案是 [3,-2,1,-5,2,-4]。

先排个序再穿插，为什么把题目要的顺序毁了

一个自然的念头是先按正负排序、把正负数分到两头，再一正一负交错取。可题目死死要求同号元素保持原来的先后，排序按数值大小重洗，3、1、2 会变成 1、2、3，先后全乱、直接答错。退一步，先扫一遍把正数收一摞、负数收一摞，再交替从两摞取——这能保住顺序，也是 O(n)，只是要两遍扫描加两个列表。有没有一遍到位、不必先攒两堆的走法？

正负交替这个要求，其实把每个数的落点钉死了

把答案的位置从 0 开始编号看一遍：偶数下标 0、2、4 和奇数下标 1、3、5，天生就一个隔一个交替出现。要让相邻两数一正一负，等价于让所有正数占满偶数下标、所有负数占满奇数下标。又因为最小的下标 0 是偶数位，第一个正数正好坐在开头，正数打头自动满足。于是「正负交替」被翻译成两条互不打扰的下标轨道：正数走 0、2、4……，负数走 1、3、5……。

两个写指针各管一条轨道，遍历一遍就分派完

另开一张与 nums 等长的结果数组 ans，摆两个写指针：i 从偶数位 0 起、专写正数，j 从奇数位 1 起、专写负数。扫一遍 nums，每读到一个数只问符号：正数写进 ans[i]、随后 i 加二到下一个偶数位；负数写进 ans[j]、随后 j 加二到下一个奇数位。两条轨道各走各的、互不干涉，扫完 ans 就填满，同号的数按遇到的先后落坑，顺序原样保住。

跟着 [3,1,-2,-5,2,-4] 把两条轨道走一遍

起手 i 在偶数位 0、j 在奇数位 1，ans 六个坑全空。读到 3，正数，落进 ans[0]，i 加二挪到 2。读到 1，正数，落进 ans[2]，i 挪到 4。读到 -2，负数，落进 ans[1]，j 加二挪到 3。读到 -5，负数，落进 ans[3]，j 挪到 5。读到 2，正数，落进 ans[4]，i 挪到 6。读到 -4，负数，落进 ans[5]，j 挪到 7。ans 收成 [3,-2,1,-5,2,-4]：偶数位是 3、1、2，奇数位是 -2、-5、-4，同号先后没动，与题面答案一致。

指针加一还是加二，一步之差就互相覆盖

复杂度干脆：从头到尾只扫一遍 nums，每个数一次符号判断加一次写入，都是常数活，时间 O(n)；额外开了一张等长的 ans，空间 O(n)。题目本就允许不原地做，这张结果数组换来直白的分派。

落笔前有几处容易崴脚。写指针每次必须加二、不能加一——偶数位隔着一个奇数位才是下一个偶数位，加一会踩进异号的坑、把刚写的盖掉。正数配偶数位、负数配奇数位也别记反，一旦对调，开头就成了负数，题目要的正数打头当场破功。还有个反直觉的地方：哪怕原数组里负数比正数先出现，负数照样只认奇数位、正数只认偶数位，开头永远是正数，谁先出场都不改归属。

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

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

Java

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