[LintCode] 64 Merge Sorted Array 解题报告

Description
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里放。
当任意一个数组的数字放完的时候，判断一下：
如果数组A的数字放完了，那么要把数组B里剩下的数字放到A里。


Code

class Solution {
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        // write your code here
        
        int index = m + n - 1;
        m--;
        n--;
        while (m >= 0 && n >= 0) {
            if (A[m] > B[n]) {
                A[index--] = A[m--];
            }
            else {
                A[index--] = B[n--];
            }
        }
        if (m < 0) {
            for (int i = 0; i <= n; i++) {
                A[i] = B[i];
            }
        }
    }
}