题目
描述
合并两个排序的整数数组A和B变成一个新的数组。
样例
给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]
解答
思路
归并排序。建立新的数组，大小为两个数组长度之和。
从后往前归并，好处在于，如果大的数组长度足够容纳所有的元素，可以降低空间复杂度。
代码
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[] C = new int[A.length+B.length];
int i = A.length - 1, j = B.length - 1, k = A.length + B.length-1;
while(i >= 0 && j >= 0){
C[k--] = (A[i] < B[j]) ? B[j--] : A[i--];
}
while(i>=0){
C[k--] = A[i--];
}
while(j>=0){
C[k--] = B[j--];
}
return C;
}
}
