88. 合并两个有序数组(两种思路：C实现)

88. 合并两个有序数组(两种思路：C实现)

文章目录

• 题目
• 思路1--开辟额外空间
• 思路2--双指针从后往前合并

题目

题目链接：88. 合并两个有序数组

思路1–开辟额外空间

我们直到要想合并两个数组：最简单的方式就是开辟一个新空间nums;
然后，从头开始：nums1和nums2比较，小的放到nums中即可；
同时要注意：可以有nums1放完和nums2没放完的情况；还有nums2放完，nums1没放完的情况。
最后再把nums的值拷贝回去nums1即可；

---

时间复杂度O（n+m）;
空间复杂度O（n+m）;

---

实现代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int first = 0; //nums1的下标
	int second = 0; //nums2的下标
	//开辟大小为m+n的数组，为的是能够容纳nums1和nums2的值
	int* nums  = (int*)malloc(sizeof(int)*(m+n));
	int third = 0; //nums的数组下标
	
	while(first < m && second < n) //在不越界的情况下，都继续循环
	{		
		if(nums1[first] < nums2[second]){
			nums[third++] = nums1[first++]; //赋值时候不要忘记下标的移动
		}else{
			nums[third++] = nums2[second++];
		}
	}
	//退出循环后，要考虑nums1和nums2哪个没有赋值完到nums中
	while(first < m) //退出循环后，first < m说明nums1还没有赋值完到nums中
	{
		nums[third++] = nums1[first++];	
	}
	while(second < n)//退出循环后，second < n说明nums1还没有赋值完到nums中
	{
		nums[third++] = nums2[second++];
	}
	
	//最后把nums的值拷贝回去nums1中
	memcpy(nums1,nums,sizeof(int)*(m+n));
	free(nums);
}

---

思路2–双指针从后往前合并

由于题目给出nums1的空间是比较大的，我们可以利用这个特性，合并到nums1中，不需要开辟额外的空间。
这次我们从后往前合并：
从nums1和nums2的有效数据后面，哪个大的就放到nums1的最后面；
退出时候也要判断以下：假如nums1放完了，nums2还没放完，直接把nums2的都赋值过去给nums1即可；

---

时间复杂度O(n+m);
空间复杂度O(1);

---

代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int end1 = m -1; //指向nums1的有效位的最后一个元素
	int end2 = n -1; //指向nums2的最后一个元素
	int dst = nums1Size -1;
	while(end1 >=0 && end2 >= 0) //在该条件下，循环继续
	{
		//把大的值赋给nums1的后面
		if(nums1[end1]>nums2[end2]){
			nums1[dst--] = nums1[end1--];
		}else{
			nums1[dst--] = nums2[end2--];
		}
	}
	//退出循环后,nums2还没结束
	while(end2 >= 0){
		nums1[dst--] = nums2[end2--];
	}
}

---