描述

给出一个整数数组 和有序的整数数组 ,请将数组 合并到数组 中,变成一个有序的升序数组
注意:

  1. 可以假设 数组有足够的空间存放 数组的元素, 和 中初始的元素数目分别为 和 ,的数组空间大小为 +
  2. 不要返回合并的数组,返回是空的,将数组 的数据合并到里面就好了
  3. 数组在[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)

最后

这道题整体难度不大,只要想到从后往前处理的逻辑就可以
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。

图片说明