描述

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

樣例

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

挑戰(zhàn)

你能否優(yōu)化你的算法，如果其中一個數(shù)組很大而另一個數(shù)組很小？

代碼

public class Solution {
    /*
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    public int[] mergeSortedArray(int[] A, int[] B) {
        if (A == null || B == null) {
            return null;
        }
        
        int[] results = new int[A.length + B.length];
        int i = 0, j = 0, index = 0;
        while (i < A.length && j < B.length) {
            if (A[i] < B[j]) {
                results[index] = A[i];
                i++;
            // A[i] == B[j]情況分兩次記錄，先記錄B[j]，j 變化 i 不變再記錄A[i]
            } else {
                results[index] = B[j];
                j++;
            }
            index++;
        }

        // 用while循環(huán)，不能用if
        while (i < A.length) {
            results[index] = A[i];
            i++;
            index++;
        }
        while (j < B.length) {
            results[index] = B[j];
            j++;
            index++;
        }
        return results;
    }
}