合并两个有序数组

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

链接：https://leetcode-cn.com/problems/merge-sorted-array/

题目要求：

注意：

• 要合并的两个数组都是有序的
• num1数组的长度为m+n ->即合并在num1数组中
• 合并后的数组也是非递减的(非降序)

方法1：空间换时间

==思路==：开辟一个m+n大小的数组用来存放合并后的数据

• 排成非降序的，所以：
• num1和num2数组的元素进行比较，把小的拷贝到新数组中
• 因为总有一个数组的元素先拷贝完成，所以要进行判断哪个数组先拷贝结束，然后把另一个数组的元素接着拷贝
• 把新数组的元素拷贝回去num1数组中，最后释放动态开辟的空间，并且把指针置空

代码

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int* arr = (int*)malloc(sizeof(int) * nums1Size);
	if (arr == NULL)
	{
		printf("malloc fail\n");
		return;
	}
	int i = 0;	//控制num1下标
	int j = 0;	//控制num2下标
	int k = 0;//控制arr下标
    
    //i<m && j<n 防止越界
	while (i < m && j < n)
	{
        //num2小，就把num2元素放到arr数组
		if (nums1[i] > nums2[j])
		{
			arr[k] = nums2[j];
			k++;
			j++;
		}
		else
		{
            //num1小，就把num1元素放到arr数组
			arr[k] = nums1[i];
			k++;
			i++;
		}
	}
	//判断谁先结束，下面两个while循环只执行1个
	while (i < m)
	{
		arr[k] = nums1[i];
		k++;
		i++;
	}

	while (j < n)
	{
		arr[k] = nums2[j];
		k++;
		j++;
	}
    //拷贝回去
	for (i = 0; i < nums1Size; i++)
	{
		nums1[i] = arr[i];
	}
    //最后释放动态开辟的空间，并且把指针置空
    free(arr);
    arr = NULL;
}

方法2：排序

==思路==：把nums2数组的数据拷贝到num1数组后面，然后对nums1数组元素进行排序(排成升序)

代码

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int end1 = m - 1;// num1前面有内容最后元素的下标
	int end2 = n - 1;//num2最后一个元素的下标
	int end = m + n - 1;//num1最后元素的下标
	int i = 0;
	int j = 0;
	//将num2的内容拷贝到num1的后面
	for (i = 0; i < n; i++)
	{
		nums1[end] = nums2[i];
		end--;
	}
	//排序
	for (i = 0; i < m + n-1; i++)
	{
		for (j = 0; j < m + n -1- i; j++)
		{
			if (nums1[j + 1] < nums1[j])
			{
				int  tmp = nums1[j];
				nums1[j] = nums1[j + 1];
				nums1[j + 1] = tmp;
			}
		}
	}
}

方法3：三指针

==思路==：

使用三个下标控制两个数组：

• end：nums1数组最后一个元素位置下标
• end1：nums1数组有效数字的最后一个元素位置下标
• end2：nums2数组最后一个元素下标

• 从两个数组的最后一个元素比较(因为两个数组都是非递减数组)
• end1和end2指向的元素进行比较，把大的放在end位置，然后对应end1或者end2下标–，end也要–
• end1和end2总有一个先不满足条件：(end1>=0 && end2>=0)
  • 如果是nums2数组还未拷贝完成(end2>=0了)，就继续拷贝
  • 如果是nums1数组还未拷贝完成， 就不用管了，因为原来的nums1数组是有序的

代码

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];
			end1--;
			end--;
		}
		else
		{
			nums1[end] = nums2[end2];
			end2--;
			end--;
		}
	}
	//有一个先结束
	//当nums1剩余元素没有拷贝时 不用处理，因为nums1数组本身就是有序的
	//当剩余元素没有拷贝的是num2数组：nums2接着拷贝
	while (end2 >= 0)
	{
		nums1[end] = nums2[end2];
		end--;
		end2--;
	}
}