1389. 按既定顺序创建目标数组

🟢   🔖  数组 模拟  🔗 力扣 LeetCode

题目

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

• Initially target array is empty.
• From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
• Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]

Output: [0,4,1,3,2]

Explanation:

nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]

Output: [0,1,2,3,4]

Explanation:

nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]

Output: [1]

Constraints:

• 1 <= nums.length, index.length <= 100
• nums.length == index.length
• 0 <= nums[i] <= 100
• 0 <= index[i] <= i

题目大意

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：

• 目标数组 target 最初为空。
• 按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
• 重复上一步，直到在 nums 和 index 中都没有要读取的元素。

请你返回目标数组。

题目保证数字插入位置总是存在。

示例 1：

输入： nums = [0,1,2,3,4], index = [0,1,2,2,1]

输出：[0,4,1,3,2]

解释：

nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

示例 2：

输入： nums = [1,2,3,4,0], index = [0,1,2,3,0]

输出：[0,1,2,3,4]

解释：

nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

示例 3：

输入： nums = [1], index = [0]

输出：[1]

提示：

• 1 <= nums.length, index.length <= 100
• nums.length == index.length
• 0 <= nums[i] <= 100
• 0 <= index[i] <= i

解题思路

1. 初始化目标数组 res：

   • 定义一个空数组 res 用于存储构造结果。

2. 遍历数组：

   • 对数组 nums 和 index 进行同步遍历。
   • 使用 res.splice(index[i], 0, nums[i]) 在目标位置 index[i] 插入元素 nums[i]：
     • splice 函数的第一个参数是插入位置。
     • 第二个参数是要删除的元素个数（这里为 0，因为不删除任何元素）。
     • 第三个参数是要插入的值。

3. 返回结果：

   • 遍历完成后，返回数组 res。

复杂度分析

• 时间复杂度：O(n^2)

  • 每次插入操作的时间复杂度为 O(k)，其中 k 是插入位置之后的元素个数。
  • 在最坏情况下，对于长度为 n 的数组，插入操作的总时间复杂度为 O(n^2)。

• 空间复杂度：O(n)，使用额外的数组 res 存储结果数组。

代码

/**
 * @param {number[]} nums
 * @param {number[]} index
 * @return {number[]}
 */
var createTargetArray = function (nums, index) {
	let res = [];
	for (let i = 0; i < nums.length; i++) {
		res.splice(index[i], 0, nums[i]);
	}
	return res;
};