题目描述
思路解析
一句话答案：LeetCode 2149 按符号重排数组：让正数占偶数位、负数占奇数位，两个写指针一从 0、一从 1，每次跳两格，遍历原数组按符号分派，天然正负交替又保住同号先后，时间 O(n)、空间 O(n)。
重排后要正负交替、正数开头，还得保住同号先后
给一个长度为偶数的数组 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)。题目本就允许不原地做，这张结果数组换来直白的分派。
落笔前有几处容易崴脚。写指针每次必须加二、不能加一——偶数位隔着一个奇数位才是下一个偶数位，加一会踩进异号的坑、把刚写的盖掉。正数配偶数位、负数配奇数位也别记反，一旦对调，开头就成了负数，题目要的正数打头当场破功。还有个反直觉的地方：哪怕原数组里负数比正数先出现，负数照样只认奇数位、正数只认偶数位，开头永远是正数，谁先出场都不改归属。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:正数排偶数位、负数排奇数位,i 和 j 各管一路、每次前进两格。下面从数组第一个元素开始,一个一个分派。
开局 · 空的结果数组与两个写指针：开局先把结果数组 ans 摆出来,六个位置现在都空着,用小点表示。两个写指针也就位了:i 停在偶数位 0,准备接正数;j 停在奇数位 1,准备接负数。它们各走各的、互不干扰。下面从 nums 的第一个元素读起。
分工 · 偶数位收正数,奇数位收负数：再把分工说清楚。ans 的偶数位 0、2、4 三个坑专留给正数,奇数位 1、3、5 三个坑专留给负数。因为下标 0 是偶数位,第一个填进去的正数就坐上了开头,正好满足以正数开头。正负各占一半坑,交替自然形成。
读 nums[0] = 3 · 先看符号：紫色指针移到 nums[0],读到的值是 3。分派之前只问一件事:它是正还是负。3 是正数,大于 0,该走偶数位这一路,交给指针 i。
正数 → 目标偶数位 ans[0]：把 nums[0] 标成绿色,提醒它是正数。正数这一路由 i 领着,i 现在指着偶数位 0,所以它的目标就是 ans[0]。右边面板用光束指向那个空槽。
落位 · ans[0] = 3 · i 前进到 2：把 3 落进 ans[0],这个坑就填实了。正数收完一个,i 加二跳到下一个偶数位 2,等着接下一个正数。 nums[0] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 1 个数。
读 nums[1] = 1 · 先看符号：紫色指针移到 nums[1],读到的值是 1。分派之前只问一件事:它是正还是负。1 是正数,大于 0,该走偶数位这一路,交给指针 i。
正数 → 目标偶数位 ans[2]：把 nums[1] 标成绿色,提醒它是正数。正数这一路由 i 领着,i 现在指着偶数位 2,所以它的目标就是 ans[2]。右边面板用光束指向那个空槽。
落位 · ans[2] = 1 · i 前进到 4：把 1 落进 ans[2],这个坑就填实了。正数收完一个,i 加二跳到下一个偶数位 4,等着接下一个正数。 nums[1] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 2 个数。
读 nums[2] = -2 · 先看符号：紫色指针移到 nums[2],读到的值是 -2。分派之前只问一件事:它是正还是负。-2 是负数,小于 0,该走奇数位这一路,交给指针 j。
负数 → 目标奇数位 ans[1]：把 nums[2] 标成红色,提醒它是负数。负数这一路由 j 领着,j 现在指着奇数位 1,所以它的目标就是 ans[1]。右边面板用光束指向那个空槽。
落位 · ans[1] = -2 · j 前进到 3：把 -2 落进 ans[1],这个坑就填实了。负数收完一个,j 加二跳到下一个奇数位 3,等着接下一个负数。 nums[2] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 3 个数。
读 nums[3] = -5 · 先看符号：紫色指针移到 nums[3],读到的值是 -5。分派之前只问一件事:它是正还是负。-5 是负数,小于 0,该走奇数位这一路,交给指针 j。
负数 → 目标奇数位 ans[3]：把 nums[3] 标成红色,提醒它是负数。负数这一路由 j 领着,j 现在指着奇数位 3,所以它的目标就是 ans[3]。右边面板用光束指向那个空槽。
落位 · ans[3] = -5 · j 前进到 5：把 -5 落进 ans[3],这个坑就填实了。负数收完一个,j 加二跳到下一个奇数位 5,等着接下一个负数。 nums[3] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 4 个数。
读 nums[4] = 2 · 先看符号：紫色指针移到 nums[4],读到的值是 2。分派之前只问一件事:它是正还是负。2 是正数,大于 0,该走偶数位这一路,交给指针 i。
正数 → 目标偶数位 ans[4]：把 nums[4] 标成绿色,提醒它是正数。正数这一路由 i 领着,i 现在指着偶数位 4,所以它的目标就是 ans[4]。右边面板用光束指向那个空槽。
落位 · ans[4] = 2 · i 前进到 6：把 2 落进 ans[4],这个坑就填实了。正数收完一个,i 加二跳到下一个偶数位 6,等着接下一个正数。 nums[4] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 5 个数。
读 nums[5] = -4 · 先看符号：紫色指针移到 nums[5],读到的值是 -4。分派之前只问一件事:它是正还是负。-4 是负数,小于 0,该走奇数位这一路,交给指针 j。
负数 → 目标奇数位 ans[5]：把 nums[5] 标成红色,提醒它是负数。负数这一路由 j 领着,j 现在指着奇数位 5,所以它的目标就是 ans[5]。右边面板用光束指向那个空槽。
落位 · ans[5] = -4 · j 前进到 7：把 -4 落进 ans[5],这个坑就填实了。负数收完一个,j 加二跳到下一个奇数位 7,等着接下一个负数。 nums[5] 变蓝,表示这一格处理完毕。目前 ans 里已经放了 6 个数。
收束 · 六个位置全部填满,答案成形：六个元素全部分派完毕。回头看一眼:偶数位 0、2、4 是 3、1、2,正是原来正数的先后;奇数位 1、3、5 是 -2、-5、-4,正是原来负数的先后。相邻两数一正一负交替,开头是正数,同号顺序原封不动。结果就是 [3,-2,1,-5,2,-4],和一开始记下的答案对上了。
边界想清:哪怕原数组负数先出现,负数照样只进奇数位、正数只进偶数位,开头永远是正数。
面试重点:双写指针一遍分派、允许 O(n) 空间不必原地、也可先分组再交替拼接。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，n 是数组长度。只从头到尾扫一遍 nums,每个元素做一次符号判断和一次写入,都是常数操作,总量随 n 线性增长
- 空间：O(n)，按峰值算。题目允许不原地修改,这里额外开了一张与 nums 等长的结果数组 ans,占用 n 个位置;两个指针只是常数,峰值就是这张 ans,量级为 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话是什么?
追问能不能做到原地、O(1) 额外空间?
追问除了双写指针,还有别的写法吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
运动员和训练师的最大匹配数
LeetCode 2410 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题