Monday, June 29, 2015

Merge Sorted Array II

Merge two given sorted integer array A and B into a new sorted integer array.
Have you met this question in a real interview? 
Yes
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?

class Solution {
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
        // write your code here
        if(A == null || B == null) return null;
        ArrayList<Integer> result = new ArrayList<Integer>();
        int i = 0, j = 0;
        while(i < A.size() || j < B.size()){
            if(i < A.size() && j < B.size()){
                if(A.get(i) <= B.get(j)){
                    result.add(A.get(i));
                    i++;
                } else {
                     result.add(B.get(j));
                     j++;
                }
            } else if(i < A.size()){
                result.addAll(A.subList(i, A.size()));
                break;
            } else if(j < B.size()){
                result.addAll(B.subList(j, B.size()));
                break;
            }
           
        }
        return result;
    }
}

No comments:

Post a Comment