合并两个排序的整数数组 A 和 B 变成一个新的数组。
注意事项:你可以假设A具有足够的空间(A数组的大小大于或等于 m + n)去添加B中的元素。 ps:m 表示 A 数组的有效元素个数,n 代表 B 数组的有效元素个数。
给出 A = [1, 2, 3, empty, empty]
, B = [4, 5]
合并之后 A 将变成 [1,2,3,4,5]
可以正序比较 A 数组与 B 数组的每一位,小的放前,其他的元素依次向后移动,但是依次向后移动这个成本太高了。
所以可以考虑倒序比较,根据数组 A 与数组 B 的最后一个有效位,进行倒序的比较,将大的添加到 A 的最后放即可。
这里要搞清楚的是 A 的最后一个有效位与 A 的最后一位的区别,A 的最后一个有效位是指 A[m-1],而 A 的最后一位是指 A[A.length-1]。
class Solution {
/**
* @param A: sorted integer array A which has m elements,
* but size of A is m+n
* @param B: sorted integer array B which has n elements
* @return: void
*/
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
int i = m - 1;
int j = n - 1;
int index = m + n -1;
while (i >= 0 && j >=0) {
if (A[i] > B[j]) {
A[index--] = A[i--];
} else {
A[index--] = B[j--];
}
}
while (i >= 0) {
A[index--] = A[i--];
}
while (j >= 0) {
A[index--] = B[j--];
}
}
}