JavaScript中按指定索引合并两个数组的高效实现方案

你的问题核心在于：indices数组中的值是元素在最终合并后数组中的位置，但直接按顺序调用splice时，前面的插入操作会改变后续元素的索引，导致无序的indices无法得到正确结果。而且多次调用splice的效率很低，每次插入都需要移动大量元素。

下面是一个更高效、无需担心indices顺序的原地实现方案：

实现思路 #

1. 将toMerge数组的元素与对应的indices配对，形成[目标位置, 元素]的数组。
2. 将配对数组按目标位置升序排序，这样我们可以从后往前处理最大的位置，避免插入操作影响前面的索引。
3. 扩展target数组的长度到最终合并后的长度（原长度 + toMerge长度）。
4. 使用三个指针从后往前遍历填充：
   • targetPtr：指向原target数组的最后一个有效元素。
   • pairPtr：指向排序后配对数组的最后一个元素（即目标位置最大的元素）。
   • currentPtr：指向当前要填充的最终数组位置。

通过从后往前填充，我们不需要移动元素，直接覆盖target数组的末尾空间（扩展后新增的undefined位置），既保证了原地修改，又大幅提升效率。

代码实现 #

function mergeArrays(target, toMerge, indices) {
    const originalTargetLength = target.length;
    const mergeLength = toMerge.length;
    const totalLength = originalTargetLength + mergeLength;

    // 配对索引与元素，并按目标位置升序排序
    const sortedPairs = toMerge
        .map((el, idx) => [indices[idx], el])
        .sort((a, b) => a[0] - b[0]);

    // 扩展target到最终长度
    target.length = totalLength;

    let targetPtr = originalTargetLength - 1;
    let pairPtr = mergeLength - 1;
    let currentPtr = totalLength - 1;

    while (currentPtr >= 0) {
        // 如果当前位置是toMerge元素的目标位置，填充它
        if (pairPtr >= 0 && sortedPairs[pairPtr][0] === currentPtr) {
            target[currentPtr] = sortedPairs[pairPtr][1];
            pairPtr--;
        } else {
            // 否则填充原target的元素
            target[currentPtr] = target[targetPtr];
            targetPtr--;
        }
        currentPtr--;
    }

    return target;
}

// 测试用例1：indices升序
const target1 = ['A', 'C', 'E', 'F', 'H'];
const toMerge1 = ['B', 'D', 'G', 'I'];
const indices1 = [1, 3, 6, 8];
mergeArrays(target1, toMerge1, indices1);
console.log(target1); // ["A","B","C","D","E","F","G","H","I"]

// 测试用例2：indices逆序
const target2 = ['A', 'C', 'E', 'F', 'H'];
const toMerge2 = ['I', 'G', 'D', 'B'];
const indices2 = [8, 6, 3, 1];
mergeArrays(target2, toMerge2, indices2);
console.log(target2); // ["A","B","C","D","E","F","G","H","I"]

复杂度分析 #

• 时间复杂度：O(m log m + n + m)，其中n是原target长度，m是toMerge长度。排序配对数组的时间是O(m log m)，填充数组的时间是O(n+m)。
• 空间复杂度：O(m)，用于存储配对数组（如果不允许额外空间，可以用原地排序，但会改变toMerge和indices的顺序，需根据需求调整）。

对比你原来的splice方法：

• 原方法时间复杂度是O(k*(n+i))（k是toMerge长度，i是每次插入移动的元素数），最坏情况为O(kn)，当数组较大时效率极低。
• 原方法无法处理无序的indices，而本方案不受indices顺序影响。

内容的提问来源于stack exchange，提问作者p40m3th3us