Merge Sorted Array -- LeetCode

這是一道數組操作的題目，思路比較明确，就是維護三個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操作，面試中可能會一起問到。