题目描述
思路解析动画文字版
记牢一句:从空列表开始,按顺序把 nums[i] 插到下标 index[i],插入会把该位置起的元素右移腾位。下面每帧都在套这句。
总览 · 空 target + 输入队列：target 现在是个空数组,右边侧栏是输入队列,把要插入的五对 (值 → 位置) 都列了出来:0 到位置 0、1 到位置 1、2 到位置 2、3 到位置 2、4 到位置 1。我们就按这个顺序一对一对地往 target 里插,每插一次它就长一格。先从第 0 步开始。
第 0 步 · 读 (值 0, 位置 0)：第 0 步,从输入队列读出这一对:要把值 0 插到下标 0。此刻 target 是 [],长度 0。
第 0 步 · 定位下标 0：插入下标是 0,正好等于 target 当前长度 0,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
第 0 步 · 接尾免移动：接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 0 放到末尾就好。
第 0 步 · 插入完成：把 0 放进空出来的下标 0,绿色就是它的新位置。target 现在变成 [0],长度涨到 1。已经插入 1 个,继续下一对。
第 1 步 · 读 (值 1, 位置 1)：第 1 步,从输入队列读出这一对:要把值 1 插到下标 1。此刻 target 是 [0],长度 1。
第 1 步 · 定位下标 1：插入下标是 1,正好等于 target 当前长度 1,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
第 1 步 · 接尾免移动：接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 1 放到末尾就好。
第 1 步 · 插入完成：把 1 放进空出来的下标 1,绿色就是它的新位置。target 现在变成 [0,1],长度涨到 2。已经插入 2 个,继续下一对。
第 2 步 · 读 (值 2, 位置 2)：第 2 步,从输入队列读出这一对:要把值 2 插到下标 2。此刻 target 是 [0,1],长度 2。
第 2 步 · 定位下标 2：插入下标是 2,正好等于 target 当前长度 2,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
第 2 步 · 接尾免移动：接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 2 放到末尾就好。
第 2 步 · 插入完成：把 2 放进空出来的下标 2,绿色就是它的新位置。target 现在变成 [0,1,2],长度涨到 3。已经插入 3 个,继续下一对。
第 3 步 · 读 (值 3, 位置 2)：第 3 步,从输入队列读出这一对:要把值 3 插到下标 2。此刻 target 是 [0,1,2],长度 3。
第 3 步 · 定位下标 2：插入下标是 2,比当前长度 3 小,说明要插到中间。紫色指针指着下标 2,这是 3 要落脚的位置,可它现在被占着,得先腾地方。
第 3 步 · 右移腾位：蓝色标出的这 1 个元素,原本占着下标 2 到 2,现在它们整体往右挪一格,空出下标 2 这个位置。这一步右移就是插入的代价所在。
第 3 步 · 插入完成：把 3 放进空出来的下标 2,绿色就是它的新位置。target 现在变成 [0,1,3,2],长度涨到 4。已经插入 4 个,继续下一对。
第 4 步 · 读 (值 4, 位置 1)：第 4 步,从输入队列读出这一对:要把值 4 插到下标 1。此刻 target 是 [0,1,3,2],长度 4。
第 4 步 · 定位下标 1：插入下标是 1,比当前长度 4 小,说明要插到中间。紫色指针指着下标 1,这是 4 要落脚的位置,可它现在被占着,得先腾地方。
第 4 步 · 右移腾位：蓝色标出的这 3 个元素,原本占着下标 1 到 3,现在它们整体往右挪一格,空出下标 1 这个位置。这一步右移就是插入的代价所在。
第 4 步 · 插入完成：把 4 放进空出来的下标 1,绿色就是它的新位置。target 现在变成 [0,4,1,3,2],长度涨到 5。已经插入 5 个,全部插完了。
完成 · target = [0,4,1,3,2]：五对都插完了,回看一遍:0、1、2 这三步插入点都正好在末尾,直接接尾;第 3 步把 3 插到下标 2,把原来的 2 挤到右边;第 4 步把 4 插到下标 1,又把 1、3、2 整体右移。最终 target 就是 [0,4,1,3,2],跟开头说的一字不差。整个过程就是照规则一步步插,没有任何技巧。
边界:单元素直接得自身;index 全 0 等于不断头插会把序列翻转;index 递增全接尾则保持原顺序。
面试重点:连续数组中间插入致 O(n²),换链表也快不了;index 范围 0 到当前长度故不越界;Java 要多一步 ArrayList 转 int[]。
参考代码
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 TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]: target = [] for x, i in zip(nums, index): target.insert(i, x) return target复杂度
- 时间：O(n²)，n 是 nums 的长度。一共要做 n 次插入,而往一个连续数组的中间插入,平均要把后面约 n 个元素右移一格,单次是 O(n),n 次合起来就是 O(n²)。本题 n 最大只有 100,这个量级毫无压力
- 空间：O(n)，总体空间 O(n),target 最终要装下全部 n 个元素。Python 和 C++ 直接把构造出来的容器作为返回结果,除它之外只用常数个循环变量;Java 这版先用 ArrayList 存完整 target 再转成返回的 int[],会有一份 O(n) 临时列表加数组转换,常数倍不改变总体 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么这道题的时间复杂度是 O(n²),能更快吗?
追问插入下标 index[i] 的取值范围是什么,为什么不会越界?
追问三种语言实现上有什么需要注意的差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
拥有最多糖果的孩子
LeetCode 1431 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题