题目描述
思路解析动画文字版
记牢这一句:正数排偶数位、负数排奇数位,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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题