照例记录下思路。
依然双指针,要求归并至 A 数组,考虑逆向归并,比较 A、B 尾部元素,大的从 A 数组索引 (A.length + B.length - 1) 开始逆向放置。最后刚好排满。
public void merge(int A[], int m, int B[], int n) { int aPtr = m - 1, bPtr = n - 1; // 两数组元素从右至左比较,大的去 A 尾部,直至有一方指针到头为止 for (int ptr = m + n - 1; aPtr >= 0 && bPtr >= 0; ptr--){ A[ptr] = A[aPtr] > B[bPtr] ? A[aPtr--] : B[bPtr--]; } // A 指针先走完的情况,B 中剩余元素直接copy至 A 对应位置即可; while (bPtr >= 0){ A[bPtr] = B[bPtr--]; } }