Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

 Notice
     You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. 
     The number of elements initialized in A and B are m and n respectively.

Example
A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

思路

• 如果从头开始比较, 那么遍历A数组的时候, 需要对比当前元素与B所有元素的大小, 才能得出结论, 时间复杂度很高.
• 反观, 空的位置在后面, 如果我们一开始比较的是两个末尾初始化好的元素, 大的放到最后的空位置, 只需要维护三个指针, O(n) 时间

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i1 = m - 1;
        int i2 = n - 1;
        int index = nums1.length - 1;

        while (i1 >= 0 && i2 >= 0) {
            if (nums1[i1] > nums2[i2]) {
                nums1[index--] = nums1[i1--];
            } else {
                nums1[index--] = nums2[i2--];
            }
        }

        while (i2 >= 0) {
            nums1[index--] = nums2[i2--];
        }
    }