題目

描述

合并兩個(gè)排序的整數(shù)數(shù)組A和B變成一個(gè)新的數(shù)組。

樣例

給出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]

解答

思路

歸并排序。建立新的數(shù)組，大小為兩個(gè)數(shù)組長(zhǎng)度之和。
從后往前歸并，好處在于，如果大的數(shù)組長(zhǎng)度足夠容納所有的元素，可以降低空間復(fù)雜度。

代碼

class Solution {
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    public int[] mergeSortedArray(int[] A, int[] B) {
        // Write your code here
        int[] C = new int[A.length+B.length];
        int i = A.length - 1, j = B.length - 1, k = A.length + B.length-1;
        while(i >= 0 && j >= 0){
            C[k--] = (A[i] < B[j]) ? B[j--] : A[i--];
        }
        while(i>=0){
            C[k--] = A[i--]; 
        }
        while(j>=0){
            C[k--] = B[j--]; 
        }
        return C;
    }
}