描述
给出一个整数数组 和有序的整数数组 ,请将数组 合并到数组 中,变成一个有序的升序数组
注意:
- 可以假设 数组有足够的空间存放 数组的元素, 和 中初始的元素数目分别为 和 ,的数组空间大小为 +
- 不要返回合并的数组,返回是空的,将数组 的数据合并到里面就好了
- 数组在[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数组
思路
这个是将两个有序的数组合并起来,并且要将结果保存在 A 数组中,这个还是比较简单想的,咱们可以从后面比较两个数组,并将结果保存在A的最后面就可以啦。
AC代码
public class Solution { public void merge(int A[], int m, int B[], int n) { // 最后数组的下*** int length = m + n - 1; // A数组的下标值 int Alen = m - 1; // B数组的下标值 int Blen = n - 1; // 当 A 和 B 数组 都没遍历完的时候 while (Alen >=0 && Blen >= 0) { // 将值大的移到A数组的末尾 A[length --] = A[Alen] > B[Blen] ? A[Alen --] : B[Blen --]; } // 如果B数组还没有遍历完,就把剩余的移到A while (Blen >= 0) { A[length --] = B[Blen --]; } } }
时间复杂度:O(Math.max(m, n)),m 和 n最大的那个
空间复杂度:O(m + n)
最后
这道题整体难度不大,只要想到从后往前处理的逻辑就可以
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。