按既定顺序创建目标数组

难度: Easy

给你两个整数数组 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

Submission

运行时间: 25 ms

内存: 16.0 MB

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        dp = [0] * len(nums)
        # print(dp)
        for i in range(len(nums)):
            dp.insert(index[i], nums[i])
        return dp[:len(nums)]

Explain

在这个题解中，我们首先创建了一个和nums等长的列表dp，初始化为全0。接着，我们遍历nums和index数组，使用Python列表的insert方法在每次迭代中将nums[i]插入到dp列表的index[i]位置。由于insert操作会导致后续元素移动，因此实际上dp列表在插入过程中长度会不断增加。最终，我们通过dp[:len(nums)]获取长度与nums相同的目标数组。这种方法直接利用了列表的动态插入特性，简化了插入的复杂度处理，但仍会涉及到元素的移动开销。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
        dp = [0] * len(nums) # 初始化目标数组dp为与nums相同长度的0数组
        for i in range(len(nums)):
            dp.insert(index[i], nums[i]) # 在index[i]位置插入nums[i]
        return dp[:len(nums)] # 截取前len(nums)长度的数组作为结果返回

Explore

这种初始化方式可能是为了简化代码或避免列表在插入操作中动态扩容的性能开销。然而，这实际上是不必要的，因为使用insert操作会导致列表自动扩容和元素移位，所以初始化为特定长度的列表并不减少复杂度。更合适的方法是直接从空列表开始，逐步插入。

insert操作需要将指定位置及其之后的所有元素向后移动一位来为新元素腾出空间，这是一个O(n)的操作，其中n是列表当前的长度。因此，如果在列表的开始位置频繁插入，每次操作的成本较高。在最坏情况下，如果总是在列表的前端插入，整体时间复杂度将达到O(n^2)，其中n是插入操作的次数。

这一步骤是不必要的，因为如果dp列表初始化为空列表，并正确使用insert插入元素，则dp的最终长度应直接等于nums的长度，无需截取。这个步骤在题解中的存在可能是为了确保结果的长度正确，尤其是在初始化为固定长度并可能通过insert超出原始长度的情况下。但正确的处理方式应该是从空列表开始，并且直接使用插入后的dp列表。

如果index数组中存在重复的值，那么每次插入都会在相同的位置插入新元素，前面插入的元素将被推后。例如，如果两次都插入到位置0，第一次插入的元素将移动到位置1，新元素将占据位置0。因此，最终数组的元素顺序将根据插入的顺序和index的值动态决定，后插入的元素会位于同位置的前面。