重新排列数组 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,3,4], n=2
- 输出
- [1,3,2,4]
- 输入
- nums=[5,9], n=1
- 输出
- [5,9]
- 输入
- nums=[1,1,2,2], n=2
- 输出
- [1,2,1,2]
最优解：一步一步想明白
- 3记牢一句:配对的两个数相隔 n,nums[i] 落答案第 2i 位、nums[i+n] 落第 2i+1 位,i 扫一遍就交替拼好。下面每帧都在套这句。
- 4先看清布局。上面是源数组 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 位开始。
- 5答案第 0 位该放 x 组第 1 个。紫色指针落在源数组下标 0,值是 3。它就是这一对里的 x,稍后它的搭档 nums[5] 会紧跟着补到它后面。
- 6把 3 写进答案的第 0 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3]。已经排好 1 个,接着补它的搭档 y。
- 7答案第 1 位该放 y 组第 1 个。紫色指针跳到源数组下标 5,也就是上一个 x 往后数 5 格的位置,值是 4。它是刚才那个 x 的搭档,要紧挨着补在它后面。
- 8把 4 写进答案的第 1 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4]。已经排好 2 个,这一对凑齐了,换下一对的 x。
- 9答案第 2 位该放 x 组第 2 个。紫色指针落在源数组下标 1,值是 8。它就是这一对里的 x,稍后它的搭档 nums[6] 会紧跟着补到它后面。
- 10把 8 写进答案的第 2 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8]。已经排好 3 个,接着补它的搭档 y。
- 11答案第 3 位该放 y 组第 2 个。紫色指针跳到源数组下标 6,也就是上一个 x 往后数 5 格的位置,值是 7。它是刚才那个 x 的搭档,要紧挨着补在它后面。
- 12把 7 写进答案的第 3 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7]。已经排好 4 个,这一对凑齐了,换下一对的 x。
- 13答案第 4 位该放 x 组第 3 个。紫色指针落在源数组下标 2,值是 1。它就是这一对里的 x,稍后它的搭档 nums[7] 会紧跟着补到它后面。
- 14把 1 写进答案的第 4 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1]。已经排好 5 个,接着补它的搭档 y。
- 15答案第 5 位该放 y 组第 3 个。紫色指针跳到源数组下标 7,也就是上一个 x 往后数 5 格的位置,值是 2。它是刚才那个 x 的搭档,要紧挨着补在它后面。
- 16把 2 写进答案的第 5 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2]。已经排好 6 个,这一对凑齐了,换下一对的 x。
- 17答案第 6 位该放 x 组第 4 个。紫色指针落在源数组下标 3,值是 6。它就是这一对里的 x,稍后它的搭档 nums[8] 会紧跟着补到它后面。
- 18把 6 写进答案的第 6 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6]。已经排好 7 个,接着补它的搭档 y。
- 19答案第 7 位该放 y 组第 4 个。紫色指针跳到源数组下标 8,也就是上一个 x 往后数 5 格的位置,值是 5。它是刚才那个 x 的搭档,要紧挨着补在它后面。
- 20把 5 写进答案的第 7 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6,5]。已经排好 8 个,这一对凑齐了,换下一对的 x。
- 21答案第 8 位该放 x 组第 5 个。紫色指针落在源数组下标 4,值是 9。它就是这一对里的 x,稍后它的搭档 nums[9] 会紧跟着补到它后面。
- 22把 9 写进答案的第 8 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6,5,9]。已经排好 9 个,接着补它的搭档 y。
- 23答案第 9 位该放 y 组第 5 个。紫色指针跳到源数组下标 9,也就是上一个 x 往后数 5 格的位置,值是 10。它是刚才那个 x 的搭档,要紧挨着补在它后面。
- 24把 10 写进答案的第 9 位,绿色标出它在源数组里已经被取走。右边 ans 现在是 [3,4,8,7,1,2,6,5,9,10]。已经排好 10 个,全部排完了。
- 25十个位置都填满了,回看一遍:答案是按 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,一对一对地交替摆,没有任何花招。
⚠️ 容易写错的地方
✗ 错：以为 nums 已经是 [x1,y1,x2,y2] 排布,直接拿相邻的 nums[2i] 和 nums[2i+1] 当一对
✓ 对：配对的两个数相隔 n:x_i 是 nums[i],搭档 y_i 是 nums[i+n]
题目说的是前一半全是 x、后一半全是 y,两组各自连续,不是交替的。配对要跨过 n 个位置去取,写成相邻取数会把同组的两个数错配成一对,结果全乱。比如 [3,8,1,6,9,4,7,2,5,10] 里和 3 配对的是下标 5 的 4,不是下标 1 的 8
✗ 错：把搭档的下标写成 i+n+1、2i 或别的偏移
✓ 对：y_i 的下标就是 i+n,落点是 ans[2i+1]
x_i 在源数组下标 i、放到答案第 2i 位;它的搭档在源数组下标 i+n、放到答案第 2i+1 位。偏移记成 i+n+1 会整体错位、还可能越界。盯住相隔 n 这个事实就不会错
✗ 错：Java 里把新数组长度开成 n,或纠结 n << 1 是什么
✓ 对：n 是长度的一半,答案长度是 2n,n << 1 就是 2n
输入有 2n 个数,答案也要 2n 个位置,开成 n 会装不下、越界。n << 1 是把 n 左移一位,等价于乘 2,只是一种算两倍的写法,Python 和 C++ 不预开定长所以没这一步
完整代码（Python / C++ / Java）
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 shuffle(self, nums: List[int], n: int) -> List[int]:
return [x for pair in zip(nums[:n], nums[n:]) for x in pair]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> shuffle(vector<int>& nums, int n) {
vector<int> ans;
for (int i = 0; i < n; ++i) {
ans.push_back(nums[i]);
ans.push_back(nums[i + n]);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] shuffle(int[] nums, int n) {
int[] ans = new int[n << 1];
for (int i = 0, j = 0; i < n; ++i) {
ans[j++] = nums[i];
ans[j++] = nums[i + n];
}
return ans;
}
}复杂度
时间
O(n)
n 是配对的对数(数组长度的一半)。从 i = 0 扫到 n-1,每对做两次常数操作把两个数放进答案,总共 2n 次常数操作,所以是线性的 O(n)。本题 n 最大 500,毫无压力
空间
O(n)
按峰值算,答案数组要装下全部 2n 个元素,这是必须交出去的输出,规模 O(n)。若不把返回结果计入,只用了循环变量和写指针等常数个空间,即 O(1) 额外空间。Python 版多切出两个临时半数组,也是 O(n) 量级,不改变结论
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 重新排列数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么搭档的下标是 i+n,这个 n 是怎么来的?+
因为题目把数组排成了前一半全是 x、后一半全是 y,两组各 n 个、各自连续。x 组第 i 个待在下标 i,跨过整整 n 个 x 才轮到 y 组,所以 y 组第 i 个就在下标 i+n。换句话说同一对的两个数在原数组里固定相隔 n,这就是整道题的钥匙,认准它,放置的下标就全清楚了。
这题能不能做到不开新数组、只用 O(1) 额外空间?+
可以,这是它的进阶玩法。因为题目里每个数都不超过 1000,小于 1024,可以借助这个上界把两个数压进同一个槽位:第一遍把每个目标位置上原值和应放的值用类似 a 加 b 乘以一个进制的方式编码到一起,第二遍再除以这个进制把重排后的值取出来。这样只在原地腾挪、不另开数组。不过对这种简单难度,直接开一个长度 2n 的答案数组、时间 O(n) 空间 O(n) 已经足够清楚,编码压位属于锦上添花的优化,面试里能讲清思路就够了。
三种语言实现上有什么差别?+
Python 最短,用 nums[:n] 和 nums[n:] 切出两组,zip 配对后双层推导式铺平,代价是多出两个切片副本。C++ 开空 vector,循环里对每个 i 先 push_back nums[i] 再 push_back nums[i+n],靠容器自己增长,最后返回。Java 不靠增长,先用 n << 1 算出 2n 一次开好定长 int 数组,再拿一个写指针 j 依次填 nums[i] 和 nums[i+n]。逻辑三家一样,只是 Python 切片加 zip、C++ 增量 push、Java 预开定长配写指针,各有各的味道。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 重新排列数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。