Sorted Merge: You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
Hints: #332
解法
比如下面两个数组：
1
2
|
A: [x1, x2, x3, _ , _ ]
B: [y1, y2]
|
两个数组都是有序的，数组A尾部有足够的空间放B数组，要求不利用临时数组，把B数组合并到A里，结果依然有序。
第一个想到的办法是两个数组从头开始比，如果B[i] < A[j]，把B[i]插入到A[j]前面。不过这个方式有两个问题：
- 每次插入都会牵涉到值copy
- 每次插入A的遍历下标都要变化
那么反过来，从两个数组的尾部开始比，谁大谁就放在尾部。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public void sortedMerge(int[] a, int aLength, int[] b) {
int aEnd = aLength - 1;
int bEnd = b.length - 1;
int i = a.length - 1;
while (aEnd >= 0 && bEnd >= 0) {
if (a[aEnd] > b[bEnd]) {
a[i] = a[aEnd];
aEnd--;
} else {
a[i] = b[bEnd];
bEnd--;
}
i--;
}
while (bEnd >= 0) {
a[i] = b[bEnd];
bEnd--;
i--;
}
}
|
评论