Description
Merge two given sorted ascending integer array A and B into a new sorted integer array.
Example
Example 1:
Input: A=[1], B=[1]
Output: [1,1]
Explanation: return array merged.
Example 2:
Input: A=[1,2,3,4], B=[2,4,5,6]
Output: [1,2,2,3,4,4,5,6]
Explanation: return array merged.
Challenge
How can you optimize your algorithm if one array is very large and the other is very small?
Solution
public int[] mergeSortedArray(int[] A, int[] B) {
if (A == null)
return B;
if (B== null)
return A;
int len = A.length + B.length;
int[] res = new int[len];
int p1 = 0;
int p2 = 0;
int index = 0;
while(p1 < A.length && p2 < B.length){
// 谁大就先插入谁
if(A[p1] < B[p2]){
res[index] = A[p1];
p1++;
index++;
}else{
res[index] = B[p2];
p2++;
index++;
}
}
// 把另一个数组中剩下的元素也插入到结果数组中
while(p1 < A.length){
res[index] = A[p1];
p1++;
index++;
}
while(p2 < B.length){
res[index] = B[p2];
p2++;
index++;
}
return res;
}