合并两个升序数组A和B到数组A

题目

给出两个有序的整数数组A（长度m）和B(长度n) ，请将AB数组合并到数组A中，变成一个有序的数组。

算法思路

1. 合并后数据总长度m+n，最后一个元素的位置为A[m+n-1]
2. 从前（下标0）向后（下标m-1，n-1）合并需要挪动后续元素，复杂度高。因此，我们从后向前合并。
3. 如何合并？初始化当前合并下标lastPos = m+n-1, 当前A数组下标posA = m-1, 当前B数组下标posB = n-1
4. 逐个比大小，A[posA]和B[posB]取较大元素，放入A[lastPos]。取A数组，则posA--； 取B数组则posB--。同时lastPos--
5. 最后如果B数组有剩余，填入A数组即可

关于4和5，如果想问为什么这样就可以达到目的。注意观察，原始A数组中特定位置的数据，要么保持原位不变，要么会向后移动。因此，我们只需要取最大元素，放入lastPos即可

代码实现

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int posA = m-1;
        int posB = n-1;
        int lastPos = m + n - 1;

        while(posA >= 0 && posB >= 0){
            if( A[posA] >= B[posB] ){
                A[lastPos] = A[posA];
                posA --;
            }else{
                A[lastPos] = B[posB];
                posB --;
            }
            lastPos --;
        }

        while(posB >= 0){
            A[lastPos] = B[posB];
            posB -= 1;
            lastPos -= 1;
        }
    }
}