时间复杂度O(m+n)
    空间复杂度O(1)

    1. class Solution {
    2. public:
    3.     void merge(int A[], int m, int B[], int n) {
    4.         // 从后往前开始合并，不需要开辟额外的空间和大量的移位操作
    5.         int idx = m+n-1;
    6.         // 两个数组合并完的长度是m+n，所以从数组A的m+n-1处开始往前存放元素
    7.         int i = m-1, j = n-1;
    8.         while (i >= 0 && j >= 0) {
    9.             // 依次比较两个数组末尾的元素，较大的值放进A的后面
    10.             if (A[i] >= B[j]) {
    11.                 A[idx--] = A[i--];
    12.             } else {
    13.                 A[idx--] = B[j--];
    14.             }
    15.         }
    16.         // while (i >= 0) A[idx--] = A[i--];
    17.         while (j >= 0) A[idx--] = B[j--];  // 最后只需要考虑B为空的情况
    18.     }
    19. };