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