leetcode
leetcode 1251 ~ 1300
按既定顺序创建目标数组

按既定顺序创建目标数组

难度:

标签:

题目描述

代码结果

运行时间: 25 ms, 内存: 16.0 MB


/*
 * 思路:
 * 1. 使用 IntStream.range() 创建索引流,然后对其进行 map 操作。
 * 2. 在 map 操作中,根据 index[i] 插入 nums[i] 到目标列表中。
 * 3. 最后将目标列表转换为数组并返回。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> target = new ArrayList<>();
        IntStream.range(0, nums.length).forEach(i -> target.add(index[i], nums[i]));
        return target.stream().mapToInt(Integer::intValue).toArray();
    }
}

解释

方法:

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

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在题解中初始化目标数组dp为与nums长度相同的全0列表,然后再使用insert操作?
这种初始化方式可能是为了简化代码或避免列表在插入操作中动态扩容的性能开销。然而,这实际上是不必要的,因为使用insert操作会导致列表自动扩容和元素移位,所以初始化为特定长度的列表并不减少复杂度。更合适的方法是直接从空列表开始,逐步插入。
🦆
在使用insert方法插入元素时,对现有元素的移动是如何影响整体性能的?
insert操作需要将指定位置及其之后的所有元素向后移动一位来为新元素腾出空间,这是一个O(n)的操作,其中n是列表当前的长度。因此,如果在列表的开始位置频繁插入,每次操作的成本较高。在最坏情况下,如果总是在列表的前端插入,整体时间复杂度将达到O(n^2),其中n是插入操作的次数。
🦆
题解中提到最终通过dp[:len(nums)]获取目标数组,为何需要这一步骤,直接使用dp数组是否可行?
这一步骤是不必要的,因为如果dp列表初始化为空列表,并正确使用insert插入元素,则dp的最终长度应直接等于nums的长度,无需截取。这个步骤在题解中的存在可能是为了确保结果的长度正确,尤其是在初始化为固定长度并可能通过insert超出原始长度的情况下。但正确的处理方式应该是从空列表开始,并且直接使用插入后的dp列表。
🦆
插入操作中如果index数组具有多个相同的值,对结果数组的最终形态有何影响?
如果index数组中存在重复的值,那么每次插入都会在相同的位置插入新元素,前面插入的元素将被推后。例如,如果两次都插入到位置0,第一次插入的元素将移动到位置1,新元素将占据位置0。因此,最终数组的元素顺序将根据插入的顺序和index的值动态决定,后插入的元素会位于同位置的前面。

相关问题