1.题目描述
给出一个有序的整数数组A 和有序的整数数组 B,请将数组B合并到数组A中,变成一个有序的升序数组。
数据范围:0 <= n,m <= 100, |A~i~| <= 100, |B~i~| <= 100
注意:
- 保证 A 数组有足够的空间存放 B 数组的元素, A 和 B 中初始的元素数目分别为 m 和 n,A的数组空间大小为 m+n
- 不要返回合并的数组,将数组 B 的数据合并到 A 里面就好了,且后台会自动将合并后的数组 A 的内容打印出来,所以也不需要自己打印
- A 数组在[0,m-1]的范围也是有序的
示例1
输入:[4,5,6],[1,2,3]
返回值:[1,2,3,4,5,6]
说明:A数组为[4,5,6],B数组为[1,2,3],后台程序会预先将A扩容为[4,5,6,0,0,0],B还是为[1,2,3],m=3,n=3,传入到函数merge里面,然后请同学完成merge函数,将B的数据合并A里面,最后后台程序输出A数组
示例2
输入:[1,2,3],[2,5,6]
返回值:[1,2,2,3,5,6]
2. 思路分析
- 题目已经明确表明,A数组足够大,那么我们就不需要开辟额外的空间,直接拿A 数组操作
- 因为是合并数组,所以就需要双指针,那么我们开辟指针i,指针j,一个指向A的
m-1
,一个指向B的n-1
,两个指针移动前我们还需要定义一个index = m + n - 1
代表合并数组的最后一个元素位置 - 开始移动,让A[i],B[j]比较谁大,谁大就合并谁
- 最后判断一下B合并完成没有,B没有合并完的话,直接把B丢进A
3. 代码
import java.util.*;
public class Solution {
public void merge(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];
index--;
i--;
} else {
A[index] = B[j];
index--;
j--;
}
}
while (i >= 0) {
A[index] = A[i];
index--;
i--;
}
while (j >= 0) {
A[index] = B[j];
index--;
j--;
}
}
}
运行结果:
4.复杂度分析
- 时间复杂度:O(m + n)
- 空间复杂度:O(1)