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

从前往后扫描，直接在A内部操作，遇到一个比A[i]小的B[j], 就把A[i:]全部后移一格。

坑：

1. 需要处理极端情况m==0和n==0。
2. 需要重新初始化A[m:]为INT最大值，避免比较出问题。

#include <limits>
class Solution {
  public:
    void merge(int A[], int m, int B[], int n) {
        int i = 0, j = 0;
        if (m == 0) {
            for (int i = 0; i < n; i++) A[i] = B[i];
            return;
        }
        if (n == 0) return;
        for(int i = m; i < m + n; i++) A[i] = numeric_limits<int>::max();
        while ( i < m + n && j < n) {
            if ( A[i] <= B[j]) {
                i++;
            } else {
                // Move A[i:] by 1
                for (int k = m + j ; k > i ; k--) {
                    A[k] = A[k - 1];
                }
                A[i] = B[j];
                j++;
            }
        }
        while (j < n) A[i++] = B[j++];
    }
};