按既定顺序创建目标数组 图解题解
这道题到底在问什么
- 输入
- nums=[1], index=[0]
- 输出
- [1]
- 输入
- nums=[1,2,3], index=[0,0,0]
- 输出
- [3,2,1]
- 输入
- nums=[4,5,6,7], index=[0,1,1,2]
- 输出
- [4,6,7,5]
最优解：一步一步想明白
- 3记牢一句:从空列表开始,按顺序把 nums[i] 插到下标 index[i],插入会把该位置起的元素右移腾位。下面每帧都在套这句。
- 4target 现在是个空数组,右边侧栏是输入队列,把要插入的五对 (值 → 位置) 都列了出来:0 到位置 0、1 到位置 1、2 到位置 2、3 到位置 2、4 到位置 1。我们就按这个顺序一对一对地往 target 里插,每插一次它就长一格。先从第 0 步开始。
- 5第 0 步,从输入队列读出这一对:要把值 0 插到下标 0。此刻 target 是 [],长度 0。
- 6插入下标是 0,正好等于 target 当前长度 0,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
- 7接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 0 放到末尾就好。
- 8把 0 放进空出来的下标 0,绿色就是它的新位置。target 现在变成 [0],长度涨到 1。已经插入 1 个,继续下一对。
- 9第 1 步,从输入队列读出这一对:要把值 1 插到下标 1。此刻 target 是 [0],长度 1。
- 10插入下标是 1,正好等于 target 当前长度 1,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
- 11接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 1 放到末尾就好。
- 12把 1 放进空出来的下标 1,绿色就是它的新位置。target 现在变成 [0,1],长度涨到 2。已经插入 2 个,继续下一对。
- 13第 2 步,从输入队列读出这一对:要把值 2 插到下标 2。此刻 target 是 [0,1],长度 2。
- 14插入下标是 2,正好等于 target 当前长度 2,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
- 15接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 2 放到末尾就好。
- 16把 2 放进空出来的下标 2,绿色就是它的新位置。target 现在变成 [0,1,2],长度涨到 3。已经插入 3 个,继续下一对。
- 17第 3 步,从输入队列读出这一对:要把值 3 插到下标 2。此刻 target 是 [0,1,2],长度 3。
- 18插入下标是 2,比当前长度 3 小,说明要插到中间。紫色指针指着下标 2,这是 3 要落脚的位置,可它现在被占着,得先腾地方。
- 19蓝色标出的这 1 个元素,原本占着下标 2 到 2,现在它们整体往右挪一格,空出下标 2 这个位置。这一步右移就是插入的代价所在。
- 20把 3 放进空出来的下标 2,绿色就是它的新位置。target 现在变成 [0,1,3,2],长度涨到 4。已经插入 4 个,继续下一对。
- 21第 4 步,从输入队列读出这一对:要把值 4 插到下标 1。此刻 target 是 [0,1,3,2],长度 4。
- 22插入下标是 1,比当前长度 4 小,说明要插到中间。紫色指针指着下标 1,这是 4 要落脚的位置,可它现在被占着,得先腾地方。
- 23蓝色标出的这 3 个元素,原本占着下标 1 到 3,现在它们整体往右挪一格,空出下标 1 这个位置。这一步右移就是插入的代价所在。
- 24把 4 放进空出来的下标 1,绿色就是它的新位置。target 现在变成 [0,4,1,3,2],长度涨到 5。已经插入 5 个,全部插完了。
- 25五对都插完了,回看一遍:0、1、2 这三步插入点都正好在末尾,直接接尾;第 3 步把 3 插到下标 2,把原来的 2 挤到右边;第 4 步把 4 插到下标 1,又把 1、3、2 整体右移。最终 target 就是 [0,4,1,3,2],跟开头说的一字不差。整个过程就是照规则一步步插,没有任何技巧。
⚠️ 容易写错的地方
✗ 错：把「插入」当成「覆盖」,直接写 target[index[i]] = nums[i]
✓ 对：是插入,要把该位置及右边元素右移腾位,长度加一
赋值会盖掉原来下标上的值、长度也不变,得到的结果完全不对。本题必须用插入语义:在下标处塞进一个新元素,后面的整体后移。比如往 [0,1,2] 的下标 2 插 3,正确是 [0,1,3,2],不是把 2 改成 3 的 [0,1,3]
✗ 错：担心 index[i] 等于当前长度会越界
✓ 对：插到等于当前长度的位置就是合法的接尾操作
插入允许的下标范围是 0 到当前长度(含两端),等于长度时就是接到末尾。题目也保证 index[i] 不超过 i,插入位置总存在,不必额外判越界
✗ 错：Java 里把 ArrayList 直接 return 给 int[] 的返回类型
✓ 对：先建一个等长 int[],把列表元素逐个拷回再返回
ArrayList<Integer> 和 int[] 是两种类型,不能直接返回。Python 的 list、C++ 的 vector 本身就是返回类型,没有这一步;Java 因为要返回基本类型数组,必须多做一次列表到数组的转换
完整代码（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 TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 targetC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#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;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
vector<int> target;
for (int i = 0; i < nums.size(); ++i) {
target.insert(target.begin() + index[i], nums[i]);
}
return target;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[] createTargetArray(int[] nums, int[] index) {
int n = nums.length;
List<Integer> target = new ArrayList<>();
for (int i = 0; i < n; ++i) {
target.add(index[i], nums[i]);
}
// return target.stream().mapToInt(i -> i).toArray();
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = target.get(i);
}
return ans;
}
}复杂度
时间
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 按既定顺序创建目标数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这道题的时间复杂度是 O(n²),能更快吗?+
因为往一个连续存储的数组中间插入,平均要把插入点后面大约一半的元素往右挪,单次插入就是 O(n) 量级,一共插 n 次,所以是 O(n²)。想绕开右移可以改用链表,链表在已知位置插入是 O(1),但你得先走到那个下标,定位又是 O(n),整体并没有变快。对本题这种 n 最多 100 的规模,O(n²) 的直接模拟是最清楚也最稳的写法,没必要优化。
插入下标 index[i] 的取值范围是什么,为什么不会越界?+
index[i] 的范围是 0 到当前已插入的元素个数,也就是 0 到 i 之间,题目明确保证了这一点。当 index[i] 等于当前长度时是合法的接尾,小于当前长度时是插到中间,这两种都在插入接口允许的范围内,所以不需要额外的边界判断,直接调用插入就行。
三种语言实现上有什么需要注意的差别?+
Python 用 list.insert,C++ 用 vector.insert,它俩的容器本身就是返回类型,插完直接返回。Java 这版用 ArrayList 的 add 带下标插入,逻辑一样,但题目要求返回 int 数组,而 ArrayList 装的是 Integer 对象,不能直接返回,得最后再开一个等长的 int 数组,把元素逐个拷回去。这是 Java 比另外两家多出来的一步收尾。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 按既定顺序创建目标数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。