合并排序数组

题意

合并两个排序的整数数组A和B变成一个新的数组。

样例

给出A = [1,2,3,4],B = [2,4,5,6],返回 [1,2,2,3,4,4,5,6]

思路

创建一个新的数组,长度是 A 和 B 长度之合,再设三个指针,分别指向 A,B 和新数组的第一个元素,然后遍历两个数组,依次比较每一个元素,较小的数存入新数组中,并将较小值的指针与新数组的指针向后移动一位。最后当遍历完 A 或 B 以后,就将剩余数组的数据依次添加到新数组。

代码实现

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
30
31
32
33
34
35
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) {
if (A == null || B == null) {
return null;
}

int[] result = new int[A.length + B.length];

int i = 0;
int j = 0;
int index = 0;

while (i < A.length && j < B.length) {
if (A[i] < B[j]){
result[index++] = A[i++];
} else {
result[index++] = B[j++];
}
}

while (i < A.length) {
result[index++] = A[i++];
}

while (j < B.length) {
result[index++] = B[j++];
}

return result;
}
}

原题地址

LintCode:合并排序数组

坚持原创技术分享,您的支持将鼓励我继续创作!