基于排列构建数组 图解题解
这道题到底在问什么
- 输入
- nums=[0,2,1,5,3,4]
- 输出
- [0,1,2,4,5,3]
- 输入
- nums=[5,0,1,2,3,4]
- 输出
- [4,5,0,1,2,3]
最优解：一步一步想明白
- 3记牢这套两层取值:先用 nums[i] 拿到下标 j,再用 nums[j] 拿到真正要填的值。下面从第 0 位开始,一位一位地走。
- 4先摆好战场。上面这一行是输入 nums,下标从 0 到 5,里面装的正是 0 到 5 这六个数,顺序被打乱了。右边这张表是要构建的 ans,现在每一格都写着问号,表示还没填。接下来的活儿就是从左到右,把 ans 的每一格按规则算出来。
- 5先用第 0 位把套路演示一遍。紫色框住的是当前位 i 等于 0,我们要读 nums[0]。读出来的这个数会告诉我们下一步该跳到哪个下标去。绿色标出的就是那个跳过去的落点。心里有了这个两层跳的画面,后面每一位都是重复它。
- 6来到第 0 位,紫色指针停在下标 0。第一层动作:读 nums[0],值是 0。注意这个 0 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 0 格去取真正的值。
- 7第二层动作:拿着刚才的下标 0,跳到 nums 的第 0 格,绿色框就是落点。这一位有点特别,nums[0] 正好是 0,跳过去落在的还是它自己这一格。这一格里装的是 0,这才是要填进 ans[0] 的值。
- 8把 0 写进 ans[0]。右边那张表第 0 行的问号,现在换成了 0,点亮了。整条链路串起来就是 ans[0] 等于 nums[nums[0]],等于 nums[0],等于 0。这一位搞定,指针往右挪一格。
- 9来到第 1 位,紫色指针停在下标 1。第一层动作:读 nums[1],值是 2。注意这个 2 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 2 格去取真正的值。
- 10第二层动作:拿着刚才的下标 2,跳到 nums 的第 2 格,绿色框就是落点。这一格里装的是 1,这才是要填进 ans[1] 的值。
- 11把 1 写进 ans[1]。右边那张表第 1 行的问号,现在换成了 1,点亮了。整条链路串起来就是 ans[1] 等于 nums[nums[1]],等于 nums[2],等于 1。这一位搞定,指针往右挪一格。
- 12来到第 2 位,紫色指针停在下标 2。第一层动作:读 nums[2],值是 1。注意这个 1 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 1 格去取真正的值。
- 13第二层动作:拿着刚才的下标 1,跳到 nums 的第 1 格,绿色框就是落点。这一格里装的是 2,这才是要填进 ans[2] 的值。
- 14把 2 写进 ans[2]。右边那张表第 2 行的问号,现在换成了 2,点亮了。整条链路串起来就是 ans[2] 等于 nums[nums[2]],等于 nums[1],等于 2。这一位搞定,指针往右挪一格。
- 15来到第 3 位,紫色指针停在下标 3。第一层动作:读 nums[3],值是 5。注意这个 5 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 5 格去取真正的值。
- 16第二层动作:拿着刚才的下标 5,跳到 nums 的第 5 格,绿色框就是落点。这一格里装的是 4,这才是要填进 ans[3] 的值。
- 17把 4 写进 ans[3]。右边那张表第 3 行的问号,现在换成了 4,点亮了。整条链路串起来就是 ans[3] 等于 nums[nums[3]],等于 nums[5],等于 4。这一位搞定,指针往右挪一格。
- 18来到第 4 位,紫色指针停在下标 4。第一层动作:读 nums[4],值是 3。注意这个 3 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 3 格去取真正的值。
- 19第二层动作:拿着刚才的下标 3,跳到 nums 的第 3 格,绿色框就是落点。这一格里装的是 5,这才是要填进 ans[4] 的值。
- 20把 5 写进 ans[4]。右边那张表第 4 行的问号,现在换成了 5,点亮了。整条链路串起来就是 ans[4] 等于 nums[nums[4]],等于 nums[3],等于 5。这一位搞定,指针往右挪一格。
- 21来到第 5 位,紫色指针停在下标 5。第一层动作:读 nums[5],值是 4。注意这个 4 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 4 格去取真正的值。
- 22第二层动作:拿着刚才的下标 4,跳到 nums 的第 4 格,绿色框就是落点。这一格里装的是 3,这才是要填进 ans[5] 的值。
- 23把 3 写进 ans[5]。右边那张表第 5 行的问号,现在换成了 3,点亮了。整条链路串起来就是 ans[5] 等于 nums[nums[5]],等于 nums[4],等于 3。这一位搞定,指针往右挪一格。
- 24六位全部走完,回放一遍。ans 从头到尾是 [ 0, 1, 2, 4, 5, 3 ]。每一位都靠同一招:先用 nums[i] 拿到一个下标,再用那个下标去 nums 里取一次值。整个过程只从左到右扫了一遍,没有回头。
- 25再抽第 3 位复核一下,这一位跨度最大,最能说明问题。nums[3] 是 5,于是跳到下标 5,nums[5] 是 4,所以 ans[3] 等于 4。和题面里那串解释完全对得上。别的位你也可以照这个法子自己验一遍。
⚠️ 容易写错的地方
✗ 错：把 ans[i] 写成 nums[i],只取一层
✓ 对：ans[i] = nums[nums[i]],要取两层下标
题目要的是拿 nums[i] 当下标再取一次,少一层就完全错了
✗ 错：担心 nums[i] 当下标会越界
✓ 对：排列保证每个值都在 0 到 n 减 1,天然合法
nums 是 0 到 n 减 1 的排列,任何元素当下标都落在范围内,不会越界
✗ 错：原地把 ans 写回 nums 覆盖原值
✓ 对：想省空间时要用编码技巧,不能直接覆盖
直接覆盖会把还没用到的 nums 值改掉,后面的位就读到错误值了
完整代码（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 buildArray(self, nums: List[int]) -> List[int]:
return [nums[num] for num in nums]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> buildArray(vector<int>& nums) {
vector<int> ans;
for (int& num : nums) {
ans.push_back(nums[num]);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] buildArray(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
ans[i] = nums[nums[i]];
}
return ans;
}
}复杂度
时间
O(n)
n 是数组长度。从头到尾扫一遍,每一位做两次下标读取和一次写入,都是常数操作,总量随长度线性增长
空间
O(n)
按峰值算。这版额外开了一个和 nums 等长的 ans 存结果,是 O(n)。若不把返回数组计入,则只用常数个变量;进阶要求的 O(1) 额外空间要靠原地编码技巧另算
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 基于排列构建数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题最朴素的做法是什么?+
开一个和 nums 等长的 ans,从头到尾遍历,每一位算 ans[i] = nums[nums[i]],先用 nums[i] 拿到下标再取一次值。时间 O(n),额外空间 O(n)。写法直接,面试里先给出这版最稳。
进阶要求 O(1) 额外空间,怎么做?+
用一个编码技巧:因为每个 nums[i] 都小于 n,可以把新值和旧值压进同一个格子。第一遍令 nums[i] 加上 n 乘以 nums[nums[i]] 对 n 取余的结果,这样一个数里同时藏着旧值取余 n 和新值。第二遍再让每个 nums[i] 除以 n,取出新值。全程只在原数组上改,不额外开表,达到 O(1) 额外空间。
为什么编码时要对 n 取余?+
因为遍历到后面的位时,前面的 nums 已经被加大了,直接读会读到被污染的数。对 n 取余能还原出那一格的原始值,保证取到的是编码前的 nums[nums[i]],这样两遍法才正确。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 基于排列构建数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。