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?
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) {
int i = 0;
int j = 0;
int k = 0;
int[] result = new int[A.length + B.length];
while(i < A.length && j < B.length){
if(A[i] <= B[j]){
result[k++] = A[i];
i++;
}else{
result[k++] = B[j];
j++;
}
}
if(i == A.length){
for(int l = j; l < B.length; l++){
result[k++] = B[l];
}
}else{
for(int m = i ; m < A.length; m++){
result[k++] = A[m];
}
}
return result;
}
}
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) {
// write your code here
if (A.length == 0 || A == null){
return B;
}
if (B.length == 0 || B == null){
return A;
}
int len = A.length + B.length;
int[] res = new int[len];
if(A.length >= B.length) {
for(int i=0;i<A.length;i++) {
res[i] = A[i];
}
for(int i=0;i<B.length;i++) {
res[A.length + i] = B[i];
}
}else {
for(int i=0;i<B.length;i++) {
res[i] = B[i];
}
for(int i=0;i<A.length;i++) {
res[B.length + i] = A[i];
}
}
Arrays.sort(res);
return res;
}
}
描述
合并两个排序的整数数组A和B变成一个新的数组。
您在真实的面试中是否遇到过这个题？
样例
给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]