题目描述
思路解析
一句话答案：LeetCode 1920 基于排列构建数组：对每个下标 i 求 ans[i]=nums[nums[i]]，先用 nums[i] 拿到下标、再取一次值的二次取值，从头扫一遍即可，时间 O(n)、空间 O(n)。
排列里 ans[i] 要填两层取值的结果
给一个从 0 开始的排列 nums，也就是 0 到 n 减 1 每个数恰好出现一次、下标也从 0 起。要造一个等长的 ans，规则是对每个下标 i 都有 ans[i]=nums[nums[i]]。题面例子 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]。规则短短一行，坑就藏在那两层方括号里。
读一次 nums[i] 就填，错在哪
很多人第一眼把 ans[i] 直接写成 nums[i]，读一层就交卷。可题目要的不是 nums[i] 这个值本身，而是拿它当下标、再去 nums 里取一次。少取这一层，答案整段全错；又因为下标和值都在 0 到 n 减 1 之间、长得一模一样，肉眼还很难看出哪里填偏了。
两层取值，先拿下标再取真值
把 ans[i]=nums[nums[i]] 拆成两步就清楚了。第一层先读 nums[i]，读出来的这个数不是答案，而是一个新下标，告诉你该去 nums 的哪一格取真正的值；第二层拿这个新下标，再读一次 nums，取到的才是要填进 ans[i] 的数。
一句话记牢：先用 nums[i] 拿下标 j，再用 nums[j] 拿值。排列这个条件在这里帮了大忙——每个 nums[i] 都落在 0 到 n 减 1，当下标天然合法，永远不会越界，也就不必额外判边界。
[0,2,1,5,3,4] 每一位跳两跳落在哪
从下标 0 走起。nums[0]=0，跳到 nums 第 0 格还是 0，ans[0]=0；下标 1，nums[1]=2，跳到第 2 格取到 1，ans[1]=1；下标 2，nums[2]=1，跳到第 1 格取到 2，ans[2]=2。
接着下标 3，nums[3]=5 跨得最远，跳到第 5 格取到 4，ans[3]=4；下标 4，nums[4]=3，跳到第 3 格取到 5，ans[4]=5；下标 5，nums[5]=4，跳到第 4 格取到 3，ans[5]=3。从头到尾扫一遍不回头，ans=[0,1,2,4,5,3]，和题面对得上。
线性一遍，还能压到常数空间吗
整个过程从左到右扫一遍，每位做两次读取加一次写入，都是常数操作，时间 O(n)。另开一个等长的 ans，空间 O(n)；若不把返回数组算进去，只用几个变量。
进阶要 O(1) 额外空间，可以用一个编码技巧：因为每个值都小于 n，把新旧两个值压进同一格——第一遍给 nums[i] 加上 n 乘以 nums[nums[i]] 对 n 取余的结果，让一格里同时藏着旧值和新值；这就像把两个数塞进一个两位数，低位记旧值、乘上 n 抬到高位记新值，第二遍再整除 n，就像除掉低位、把高位的新值捞出来。对 n 取余是为了还原被加大过的原值，不然遍历到后面会取到污染数。想省空间时切记别直接把结果覆盖回 nums，没用到的原值一旦被改，后面的位就读错了。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套两层取值:先用 nums[i] 拿到下标 j,再用 nums[j] 拿到真正要填的值。下面从第 0 位开始,一位一位地走。
先摆好战场。上面这一行是输入 nums,下标从 0 到 5,里面装的正是 0 到 5 这六个数,顺序被打乱了。右边这张表是要构建的 ans,现在每一格都写着问号,表示还没填。接下来的活儿就是从左到右,把 ans 的每一格按规则算出来。
先用第 0 位把套路演示一遍。紫色框住的是当前位 i 等于 0,我们要读 nums[0]。读出来的这个数会告诉我们下一步该跳到哪个下标去。绿色标出的就是那个跳过去的落点。心里有了这个两层跳的画面,后面每一位都是重复它。
来到第 0 位,紫色指针停在下标 0。第一层动作:读 nums[0],值是 0。注意这个 0 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 0 格去取真正的值。
第二层动作:拿着刚才的下标 0,跳到 nums 的第 0 格,绿色框就是落点。这一位有点特别,nums[0] 正好是 0,跳过去落在的还是它自己这一格。这一格里装的是 0,这才是要填进 ans[0] 的值。
把 0 写进 ans[0]。右边那张表第 0 行的问号,现在换成了 0,点亮了。整条链路串起来就是 ans[0] 等于 nums[nums[0]],等于 nums[0],等于 0。这一位搞定,指针往右挪一格。
来到第 1 位,紫色指针停在下标 1。第一层动作:读 nums[1],值是 2。注意这个 2 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 2 格去取真正的值。
第二层动作:拿着刚才的下标 2,跳到 nums 的第 2 格,绿色框就是落点。这一格里装的是 1,这才是要填进 ans[1] 的值。
把 1 写进 ans[1]。右边那张表第 1 行的问号,现在换成了 1,点亮了。整条链路串起来就是 ans[1] 等于 nums[nums[1]],等于 nums[2],等于 1。这一位搞定,指针往右挪一格。
来到第 2 位,紫色指针停在下标 2。第一层动作:读 nums[2],值是 1。注意这个 1 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 1 格去取真正的值。
第二层动作:拿着刚才的下标 1,跳到 nums 的第 1 格,绿色框就是落点。这一格里装的是 2,这才是要填进 ans[2] 的值。
把 2 写进 ans[2]。右边那张表第 2 行的问号,现在换成了 2,点亮了。整条链路串起来就是 ans[2] 等于 nums[nums[2]],等于 nums[1],等于 2。这一位搞定,指针往右挪一格。
来到第 3 位,紫色指针停在下标 3。第一层动作:读 nums[3],值是 5。注意这个 5 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 5 格去取真正的值。
第二层动作:拿着刚才的下标 5,跳到 nums 的第 5 格,绿色框就是落点。这一格里装的是 4,这才是要填进 ans[3] 的值。
把 4 写进 ans[3]。右边那张表第 3 行的问号,现在换成了 4,点亮了。整条链路串起来就是 ans[3] 等于 nums[nums[3]],等于 nums[5],等于 4。这一位搞定,指针往右挪一格。
来到第 4 位,紫色指针停在下标 4。第一层动作:读 nums[4],值是 3。注意这个 3 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 3 格去取真正的值。
第二层动作:拿着刚才的下标 3,跳到 nums 的第 3 格,绿色框就是落点。这一格里装的是 5,这才是要填进 ans[4] 的值。
把 5 写进 ans[4]。右边那张表第 4 行的问号,现在换成了 5,点亮了。整条链路串起来就是 ans[4] 等于 nums[nums[4]],等于 nums[3],等于 5。这一位搞定,指针往右挪一格。
来到第 5 位,紫色指针停在下标 5。第一层动作:读 nums[5],值是 4。注意这个 4 不是答案,它是一个下标,告诉我们接下来要跳到 nums 的第 4 格去取真正的值。
第二层动作:拿着刚才的下标 4,跳到 nums 的第 4 格,绿色框就是落点。这一格里装的是 3,这才是要填进 ans[5] 的值。
把 3 写进 ans[5]。右边那张表第 5 行的问号,现在换成了 3,点亮了。整条链路串起来就是 ans[5] 等于 nums[nums[5]],等于 nums[4],等于 3。这一位搞定,指针往右挪一格。
六位全部走完,回放一遍。ans 从头到尾是 [ 0, 1, 2, 4, 5, 3 ]。每一位都靠同一招:先用 nums[i] 拿到一个下标,再用那个下标去 nums 里取一次值。整个过程只从左到右扫了一遍,没有回头。
再抽第 3 位复核一下,这一位跨度最大,最能说明问题。nums[3] 是 5,于是跳到下标 5,nums[5] 是 4,所以 ans[3] 等于 4。和题面里那串解释完全对得上。别的位你也可以照这个法子自己验一遍。
边界想清:单元素返回自身、两元素交换、整体位移的排列都按同一招逐位取值。
面试重点:朴素版 O(n) 空间最稳;进阶用同格编码加两遍法做到 O(1) 额外空间,取余是为了还原原值。
参考代码
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 buildArray(self, nums: List[int]) -> List[int]: return [nums[num] for num in nums]复杂度
- 时间：O(n)，n 是数组长度。从头到尾扫一遍,每一位做两次下标读取和一次写入,都是常数操作,总量随长度线性增长
- 空间：O(n)，按峰值算。这版额外开了一个和 nums 等长的 ans 存结果,是 O(n)。若不把返回数组计入,则只用常数个变量;进阶要求的 O(1) 额外空间要靠原地编码技巧另算
易错点
面试追问把动画讲成自己的话
追问这题最朴素的做法是什么?
追问进阶要求 O(1) 额外空间,怎么做?
追问为什么编码时要对 n 取余?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组串联
LeetCode 1929 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题