C++题解 | #合并两个有序的数组#

数组A的空间足以放置A和B中所有的元素，所以当前A中元素之后还有空间，用于放置B中元素，故而考虑从后往前进行放置。首先A中最大和B中最大进行比较，较大的放置在数组末尾，较小的依旧进行比较。以此类推，若A中元素首先被放置完毕，则将B中剩余元素直接复制进入A中即可，反之亦然，直到所有元素都放置完毕。

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        if (m == 0) {
            for (int i = 0; i < n; i++)
                A[i] = B[i];
            return ;
        }
        else {
            int i = m - 1, j = n - 1; 
            while(i >= 0 && j >= 0) {
                if (A[i] > B[j]) {
                    A[i + j + 1] = A[i];
                    i--;
                }
                else {
                    A[i + j + 1] = B[j];
                    j--;
                }
            }
            if (i >= 0) {//A中元素未放置完
        for (int t = i; t >= 0;) {
            A[t--] = A[i--];
        }
    }
    else if (j >= 0) {//B中元素未放置完
        for (int t = j; t >= 0;) {
            A[t--] = B[j--];
        }
    }
        }
    }
};