[LintCode] 6 Merge Two Sorted Arrays 解题报告

Description
Merge two given sorted integer array A and B into a new sorted integer array.



Example
A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]



Challenge
How can you optimize your algorithm if one array is very large and the other is very small?



思路
直接造一个数组，从小到大把A和B数组里的数字往里放。如果A数组的数字都放完了，就把B数组的数字全部倒进去。如果B数组的数字都放完了，就把A数组的数字全部倒进去。



Code

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 len = A.length + B.length;
        int[] res = new int[len];
        
        int i = 0;
        int j = 0;
        int index = 0;
        while (i < A.length && j < B.length) {
            if (A[i] < B[j]) {
                res[index++]  = A[i++];
            }
            else {
                res[index++] = B[j++];
            }
        }
        while (i < A.length) {
            res[index++] = A[i++];
        }
        while (j < B.length) {
            res[index++] = B[j++];
        }
        return res;
    }
}