> 文档中心 > 有序数组的合并

有序数组的合并


题目:合并两个有序数组;两个数组nums1和nums2,请你将nums2合并到nums1中,使nums1成为一个有序数组;nums1为m个元素,n为n个元素,nums1的空间大小设为m+n
注意:是把num2里面的元素放到num1中,不是创建一个新数组进行存储

解析:

    这道题目来源于力扣的第88题,因为力扣是接口型的操作方式,这里我们只给出主要的函数实现和思路解析:

例如:输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3      输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] 

那么是怎样的合并的的呢?为了防止数据被覆盖,当然是从后面开始插入;这里我们同样采用的是双指针法

具体核心代码:

代码思路分析:

我们不妨通过画图的形式进行剖析,这样更加容易理解:

    这是初始状态,接下来就是循环条件,我们要明白当两个数组从后往前移动时,不能有越界访问,所以一旦有一个数组移到下标为0的位置时,就不能往前移动了====》循环条件是:while(end1>=0 && end2 >= 0) ;然后在比较nums1[end1]nums2[end2]的大小,谁大把谁放到nums1[end]里面;最终会有两种情况:

第一种情况:end2先为0;说明num2里的数据全部已经移到num1中了,这种情况下,不用做任何的处理,具体操作步骤如下:

第二种情况:end1先为0;说明num2里的数据并没有全部移到num1中了,这种情况下,我们需要单独执行一项操作,把num2里剩余的数据拷贝到num1中;具体操作如下:

   此时是end1先=0结束;这时已经跳出循环,但是num2的数据还没有全部都插过来啊,怎么办呢?当然是单独拿出来在写一个循环,把num2剩余的数据全部插入到num1;

while(end2>=0);我们就把num2[end2]的值赋给num1[end]就可以了,之后在end--,end2--;直到所有剩余的数据全部移过去后,循环就结束啦!!!