合并排序数组 Ⅱ

题意

合并两个排序的整数数组 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]。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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--];
}
}
}

原题地址

LintCode:合并排序数组Ⅱ