题目描述
思路解析动画文字版
记牢一句:配对的两个数相隔 n,nums[i] 落答案第 2i 位、nums[i+n] 落第 2i+1 位,i 扫一遍就交替拼好。下面每帧都在套这句。
总览 · 源数组分两组 + 空答案：先看清布局。上面是源数组 nums = [3,8,1,6,9,4,7,2,5,10],下标 0 到 4 这前 5 个是 x 组,下标 5 到 9 这后 5 个是 y 组。配成一对的两个数相隔 5:比如 x 组的 3 在下标 0,它的搭档在下标 5,就是 4。右边是空的答案数组 ans,我们要按 x1,y1,x2,y2 的顺序一位一位往里填。先从答案的第 0 位开始。
第 0 位 · 读 nums[0] = 3：答案第 0 位该放 x 组第 1 个。紫色指针落在源数组下标 0,值是 3。它就是这一对里的 x,稍后它的搭档 nums[5] 会紧跟着补到它后面。
第 0 位 · 放入 3：把 3 写进答案的第 0 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3]。已经排好 1 个,接着补它的搭档 y。
第 1 位 · 读 nums[5] = 4：答案第 1 位该放 y 组第 1 个。紫色指针跳到源数组下标 5,也就是上一个 x 往后数 5 格的位置,值是 4。它是刚才那个 x 的搭档,要紧挨着补在它后面。
第 1 位 · 放入 4：把 4 写进答案的第 1 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4]。已经排好 2 个,这一对凑齐了,换下一对的 x。
第 2 位 · 读 nums[1] = 8：答案第 2 位该放 x 组第 2 个。紫色指针落在源数组下标 1,值是 8。它就是这一对里的 x,稍后它的搭档 nums[6] 会紧跟着补到它后面。
第 2 位 · 放入 8：把 8 写进答案的第 2 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8]。已经排好 3 个,接着补它的搭档 y。
第 3 位 · 读 nums[6] = 7：答案第 3 位该放 y 组第 2 个。紫色指针跳到源数组下标 6,也就是上一个 x 往后数 5 格的位置,值是 7。它是刚才那个 x 的搭档,要紧挨着补在它后面。
第 3 位 · 放入 7：把 7 写进答案的第 3 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7]。已经排好 4 个,这一对凑齐了,换下一对的 x。
第 4 位 · 读 nums[2] = 1：答案第 4 位该放 x 组第 3 个。紫色指针落在源数组下标 2,值是 1。它就是这一对里的 x,稍后它的搭档 nums[7] 会紧跟着补到它后面。
第 4 位 · 放入 1：把 1 写进答案的第 4 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1]。已经排好 5 个,接着补它的搭档 y。
第 5 位 · 读 nums[7] = 2：答案第 5 位该放 y 组第 3 个。紫色指针跳到源数组下标 7,也就是上一个 x 往后数 5 格的位置,值是 2。它是刚才那个 x 的搭档,要紧挨着补在它后面。
第 5 位 · 放入 2：把 2 写进答案的第 5 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2]。已经排好 6 个,这一对凑齐了,换下一对的 x。
第 6 位 · 读 nums[3] = 6：答案第 6 位该放 x 组第 4 个。紫色指针落在源数组下标 3,值是 6。它就是这一对里的 x,稍后它的搭档 nums[8] 会紧跟着补到它后面。
第 6 位 · 放入 6：把 6 写进答案的第 6 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6]。已经排好 7 个,接着补它的搭档 y。
第 7 位 · 读 nums[8] = 5：答案第 7 位该放 y 组第 4 个。紫色指针跳到源数组下标 8,也就是上一个 x 往后数 5 格的位置,值是 5。它是刚才那个 x 的搭档,要紧挨着补在它后面。
第 7 位 · 放入 5：把 5 写进答案的第 7 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6,5]。已经排好 8 个,这一对凑齐了,换下一对的 x。
第 8 位 · 读 nums[4] = 9：答案第 8 位该放 x 组第 5 个。紫色指针落在源数组下标 4,值是 9。它就是这一对里的 x,稍后它的搭档 nums[9] 会紧跟着补到它后面。
第 8 位 · 放入 9：把 9 写进答案的第 8 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6,5,9]。已经排好 9 个,接着补它的搭档 y。
第 9 位 · 读 nums[9] = 10：答案第 9 位该放 y 组第 5 个。紫色指针跳到源数组下标 9,也就是上一个 x 往后数 5 格的位置,值是 10。它是刚才那个 x 的搭档,要紧挨着补在它后面。
第 9 位 · 放入 10：把 10 写进答案的第 9 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6,5,9,10]。已经排好 10 个,全部排完了。
完成 · ans = [3,4,8,7,1,2,6,5,9,10]：十个位置都填满了,回看一遍:答案是按 x1,y1,x2,y2 一直到 x5,y5 的节奏拼出来的。x 组的 3、8、1、6、9 落在偶数位 0、2、4、6、8,y 组的 4、7、2、5、10 落在奇数位 1、3、5、7、9,两组交替咬合。最终 ans 就是 [3,4,8,7,1,2,6,5,9,10],跟开头说的一字不差。整个过程就是认准配对相隔 5,一对一对地交替摆,没有任何花招。
边界:n=1 只有一对、输出同输入;有重复值照样按位置交替;全相等时排完看着不变。
面试重点:搭档相隔 n 源于前后分组;进阶可借值小于 1024 编码压位做到 O(1) 额外空间;三语言差别在切片/push/定长写指针。
参考代码
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 shuffle(self, nums: List[int], n: int) -> List[int]: return [x for pair in zip(nums[:n], nums[n:]) for x in pair]复杂度
- 时间：O(n)，n 是配对的对数(数组长度的一半)。从 i = 0 扫到 n-1,每对做两次常数操作把两个数放进答案,总共 2n 次常数操作,所以是线性的 O(n)。本题 n 最大 500,毫无压力
- 空间：O(n)，按峰值算,答案数组要装下全部 2n 个元素,这是必须交出去的输出,规模 O(n)。若不把返回结果计入,只用了循环变量和写指针等常数个空间,即 O(1) 额外空间。Python 版多切出两个临时半数组,也是 O(n) 量级,不改变结论
易错点
面试追问把动画讲成自己的话
追问为什么搭档的下标是 i+n,这个 n 是怎么来的?
追问这题能不能做到不开新数组、只用 O(1) 额外空间?
追问三种语言实现上有什么差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
一维数组的动态和
LeetCode 1480 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题