动态插入排序：索引数组实现详解

golang学习网今天将给大家带来《动态插入排序：索引数组实现方法解析》，感兴趣的朋友请继续看下去吧！以下内容将会涉及到等等知识点，如果你是正在学习文章或者已经是大佬级别了，都非常欢迎也希望大家都能给我建议评论哈~希望能帮助到大家！

本文详解 LeetCode 1389 题「创建目标数组」的正确解法：根据索引数组 `index` 中指定的位置，将 `nums` 中的元素逐个插入到动态增长的目标数组中，关键在于使用 `ArrayList.add(int index, E element)` 实现 O(1) 平均复杂度的中间插入。

原题要求：给定整数数组 nums 和索引数组 index，需按顺序将 nums[i] 插入到目标数组的 index[i] 位置（即插入后该元素位于第 index[i] 个索引处，0 起始）。注意——这不是简单赋值，而是动态插入：后续插入会自动将已有元素向右推移。

你最初的实现存在两个根本性错误：

• 使用固定长度数组 int[] target = new int[nums.length]，无法支持中间插入（只能覆盖，不能平移）；
• 内层循环 for (int j = 0; j < index.length; j++) 完全冗余且逻辑错位，导致每个 nums[i] 被重复、错误地写入多个位置。

✅ 正确思路是借助动态扩容的 List（如 ArrayList），其 add(int index, E element) 方法天然支持在任意有效索引处插入，自动处理元素位移。插入完成后，再通过 Stream 转为原始 int[] 数组。

以下是完整可运行的解决方案：

import java.util.*;

public class LeetCode1389 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(createTargetArray(new int[]{0,1,2,3,4}, new int[]{0,1,2,2,1})));
        // 输出: [0, 4, 1, 3, 2]
        // 解释:
        // i=0: nums[0]=0, index[0]=0 → [] → [0]
        // i=1: nums[1]=1, index[1]=1 → [0] → [0,1]
        // i=2: nums[2]=2, index[2]=2 → [0,1] → [0,1,2]
        // i=3: nums[3]=3, index[3]=2 → [0,1,2] → [0,1,3,2]
        // i=4: nums[4]=4, index[4]=1 → [0,1,3,2] → [0,4,1,3,2]
    }

    static int[] createTargetArray(int[] nums, int[] index) {
        List<Integer> target = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            target.add(index[i], nums[i]); // 在 index[i] 处插入 nums[i]
        }
        return target.stream().mapToInt(Integer::intValue).toArray();
    }
}

? 关键点说明：

• ArrayList.add(index, element) 时间复杂度平均为 O(n)，但这是本题最优解——因为题目明确要求“插入到指定位置”，而数组无法高效支持此操作；
• 初始化 new ArrayList<>(nums.length) 是良好实践，可避免多次扩容，提升性能；
• mapToInt(Integer::intValue) 比 i -> i 更语义清晰，显式表明装箱/拆箱意图；
• 无需手动校验 index[i] 是否越界——题目已保证所有插入操作合法（0 ≤ index[i] ≤ target.size()）。

⚠️ 注意事项：

• 切勿尝试用 int[] 手动模拟插入（需频繁 System.arraycopy），代码冗长且易错；
• 若追求极致性能（如海量数据），可考虑预分配 int[] + 双指针移动，但本题场景下 ArrayList 方案简洁、健壮、符合工程实践。

总结：面对“按序插入至指定位置”类问题，优先选择支持动态索引插入的集合类型（如 ArrayList），而非硬套静态数组，这是理解抽象数据结构优势的关键一步。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。