Java高效合并两个有序数组：倒序双指针法解析

问题背景与核心难点

给定两个排序后的整型数组 A 和 B，其中数组 A 的长度足以容纳 B 中的所有元素（即 A 尾部有足够空白）。目标是编写一个方法，将 B 合并到 A 中，并保持 A 整体有序。

常见误区：
初学者往往想到直接遍历 A 和 B，将较小的元素依次放入 A 的空位或前端。若从前往后处理，当需要插入的元素位于 A 的前部时，必须将后续的已有元素全部向后平移。这种操作在数据量较大时会导致极高的时间开销，接近 O(N²)。

解决方案：倒序双指针法

第1步：分析指针位置与合并逻辑

由于 A 的尾部是空的，且两个源数组均已排序，我们可以从每个数组的最后一个有效元素开始向前比较。

• indexA：指向 A 中最后一个实际存储数据的索引。
• indexB：指向 B 中最后一个实际存储数据的索引。
• mergeIndex：指向 A 中可用于写入的最终位置，其初始值为 lastA + lastB - 1。

目的：通过从大到小填充 A 的尾部，避免覆盖尚未处理的 A 中的有效数据，从而消除元素移动的需求。

第2步：实现代码逻辑

以下是完整的 Java 实现方法。该方法接收数组及其对应的有效长度作为参数。

public static void mergeSortedArrays(int[] a, int[] b, int lastA, int lastB) {
    // 初始化三个指针分别指向各自数组的末尾
    int indexA = lastA - 1;
    int indexB = lastB - 1;
    int mergeIndex = lastA + lastB - 1;

    // 当两个数组都未遍历完时，比较当前最大值
    while (indexA >= 0 && indexB >= 0) {
        if (a[indexA] > b[indexB]) {
            // A 的当前元素较大，将其放入合并位置
            a[mergeIndex] = a[indexA];
            indexA--;
        } else {
            // B 的当前元素较大或相等，优先放入 B 的元素（稳定性考虑）
            a[mergeIndex] = b[indexB];
            indexB--;
        }
        // 合并指针前移
        mergeIndex--;
    }

    // 如果 B 中还有剩余元素，需继续复制到 A 中
    // 注意：如果 A 中还有剩余，说明它们已经在正确的位置，无需处理
    while (indexB >= 0) {
        a[mergeIndex] = b[indexB];
        mergeIndex--;
        indexB--;
    }
}

第3步：关键细节说明

1. 为何只处理 B 的剩余？
   当主循环结束时，可能出现两种情况：一是 A 先遍历完，二是 B 先遍历完。如果 A 先遍历完，剩余的 B 元素显然都比 A 中已处理的任何元素小（因为是从后往前比较），所以需要手动拷贝剩下的 B 元素。如果 B 先遍历完，剩余的 A 元素本来就在 A 的正确相对位置上（只是物理位置可能靠后，但因为是从后往前填，它们不需要动），因此无需额外操作。
2. 边界条件：
   确保传入的 lastA 和 lastB 准确对应数组中实际存储的有效元素个数，而非数组总容量。

总结

通过倒序双指针法，我们将合并两个有序数组的时间复杂度控制在 O(N+M)，空间复杂度为 O(1)（原地修改）。这种方法避免了昂贵的元素搬移操作，是解决此类面试题及实际场景中最优的标准解法。

以上就是Java高效合并两个有序数组：倒序双指针法解析的详细内容，更多关于Java数组操作与算法优化的资料请关注本站其它相关文章！