C/C++教程

leetcode 88.合并两个有序数组

本文主要是介绍leetcode 88.合并两个有序数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:给你两个按非递减顺序 排列的整数数组 nums1 和nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你合并nums2 到nums1中,使合并后的数组同样按非递减顺序排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

示例 1:
输入: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],其中斜体加粗标注的为 nums1 中的元素。

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

示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1]。合并结果是 [1] 。

注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

解析
首先我们来分析一下,nums1和nums2都是有序的,合并后的数据存储在nums1,要求合并后的nums1也是有序的

思路1:我们从头开始比较nums1和nums2中的元素,使用两个变量(begin1、begin2)分别表示这两个数组的元素下标,如果nums1[begin1] > nums2[begin2],那么nums1的所有元素向后移动一位,同时begin1++,nums2[0]放在nums1[0]位置,begin2++,然后继续比较nums1[begin1]和nums[begin2],如果nums1[begin1] < nums2[begin2],那么begin1++,继续比较nums1[begin1]和nums[begin2],…,如此反复,不断比较,然后插入数据。这种方式比较麻烦。

思路2:
从思路1中我们发现,其实是在找nums1和nums2中两个元素的较大值,因为数组是有序的,且非递减,那么我们可以从数组最后一个元素开始比较
定义3个整型变量end1表示数组nums1中元素的下标,end2表示数组nums2中元素的下标

拿第一个示例来解析:
在这里插入图片描述
nums1[end1] < nums2[end];所以nums1[end] = nums2[end2];如下图所示,6放到了nums1的最后一个元素位置
在这里插入图片描述
然后 end2–,end–,再比较nums1[end1] 和nums2[end2],nums1[end1] < nums2[end2],所以把5放在nums1的倒数第二个位置,如下图所示
在这里插入图片描述
然后end2–,end–,继续比较nums1[end1] 和nums2[end2],此时nums1[end1] > nums2[end2],所以nums1[end] = nums1[end1],3放到nums1的第3个位置,如下图
在这里插入图片描述
然后end1–;end–;继续比较nums1[end1] 和nums2[end2],nums1[end1] = nums2[end2], 然后把nums2[end2]放在nums1[end]的位置,如下如图所示:
在这里插入图片描述然后发现nums2中没有元素了,nums1剩下未比较的元素都是有序的,所以不需要再比较了,此时nums中数据为1, 2,2, 3,5, 6

所以我们总结出来如下规律:
在这里插入图片描述
我们需要通过循环来实现,那么循环的条件是什么呢?
我们发现当nums1和nums2中有一个数组中没有元素可比较了,那么循环就停止了,如果是nums2中没有元素了,那么nums1剩余元素是有序的,不需要再做任何操作;如果nums1中没有元素了,nums2中还有数据,那么将nums2中剩余的数据全部拷贝到nums1中即可

根据上述思路,我们来实现代码:
形参m表示nums1中有效数据个数,nums1Size表示nums1中元素个数,n表示nums2中数据元素个数

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int end1 = m -1;
	int end2 = n - 1;
	int end = m + n - 1;

	while((end1 >= 0)&&(end2 >=0))
	{
		if(nums1[end1] > nums2[end2])
		{
			nums1[end--] = nums1[end1--];
		}
		else
		{
			nums1[end--] = nums2[end2--];
		}		
	}
	//有一个数组没有元素了
	//如果nums2中还有数据
	while(end2 >= 0)
	{
		nums1[end--] = nums2[end2--];
	}
}
这篇关于leetcode 88.合并两个有序数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!