题目描述

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

说明:

A.length == n + m

题解

双指针

这道题是将另一个数组并入第一个数组中, 采用从后向前遍历的方法

因为两个数组都是有序的,并且数组1的空间大小是填充后新数组的空间大小. 两个数组从后开始遍历, 将较大的元素放入数组1
遍历到最后的结果有两种:

nums2遍历完,说明nums1剩余的元素就是最小的, 不用管
nums1遍历完,说明nums2剩余的元素就是最小的,需要复制到nums1中.

public void merge(int[] A, int m, int[] B, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int len = m + n - 1;

    while (p1 >= 0 && p2 >= 0) {
        A[len--] = A[p1] < B[p2] ? B[p2--] : A[p1--];
    }

    System.arraycopy(B, 0, A, 0, p2 + 1);

}