Merge Sorted Array -- LeetCode

原题链接: http://oj.leetcode.com/problems/merge-sorted-array/
这是一道数组操作的题目，思路比较明确，就是维护三个index，分别对应数组A，数组B，和结果数组。然后A和B同时从后往前扫，每次迭代中A和B指向的元素大的便加入结果数组中，然后index-1，另一个不动。代码如下：

public void merge(int A[], int m, int B[], int n) {
    if(A==null || B==null)
        return;
    int idx1 = m-1;
    int idx2 = n-1;
    int len = m+n-1;
    while(idx1>=0 && idx2>=0)
    {
        if(A[idx1]>B[idx2])
        {
            A[len--] = A[idx1--];
        }
        else
        {
            A[len--] = B[idx2--];
        }
    }
    while(idx2>=0)
    {
        A[len--] = B[idx2--];
    }        
}

这里从后往前扫是因为这个题目中结果仍然放在A中，如果从前扫会有覆盖掉未检查的元素的可能性。算法的时间复杂度是O(m+n),m和n分别是两个数组的长度，空间复杂度是O(1)。这个题类似的有Merge Two Sorted Lists，只是后者是对于LinkedList操作，面试中可能会一起问到。