让我们来看一下这道题的描述。

【题目描述】

题目：给你两个按 非递减顺序 排列的整数数组 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] 。

示例 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 中。

题目来源（力扣）：合并两个有序数组

【题目分析】

如果不考虑时间复杂度，那么最直接最暴力的方法是先将 nums2 数组拷到 nums1 数组的后面，然后再用一个简单的排序算法，就能解决问题了。但是在时间复杂度上几乎没有优势。

其实，当我们仔细再想一想，为什么给的两个数组都是有序的？直接给你两个无序数组用上面的方法不也可以解决问题吗？
因此，如果想减小时间复杂度的话，就要特别关注给的“有序数组”这个条件，在这基础上想出另一种更优的解法。

【基本思路】
我们想啊，两个数组不是都有序吗？那就先 malloc 一个用指针 tmp 指向的数组作辅助，每次只需把两个数组（都从前往后比较）当中较小的那个元素（被比较的那两个元素相等也可以，谁拷在前面谁拷在后面无所谓）拷进 tmp 数组（把这步做成一个循环），这样就可以保证 tmp 数组总是有序的。

给几个例子感受一下，（这里的 nums1 数组先不列出后面的 0 ）
用例1：nums1 = [1,4,6,8]，nums2 = [2,3,7,9]
用例2：nums1 = [9,11,14,15]，nums2 = [2,4,5,8]
用例3：nums1 = [2,4,7,9]，nums2 = [3,5]

注意一个细节，最后必定有一个数组的元素全拷进 tmp 数组了，另一个数组至少还剩下一个元素没拷进 tmp 数组。
因此，只需把那个数组还没拷的元素拷过去就行了。

题目要求将合并后的数组存储在 nums1 数组中，所以再将 tmp 数组全拷过去 nums1 数组中就行了。

【重要细节】

但是还没完！我们还要释放掉 malloc 出来的由指针 tmp 指向的数组，避免内存泄露（虽然在OJ上可以通过，不一定报错，但是我们还是要保持这个习惯，因为内存泄露的后果还是比较严重的）

最后把指针 tmp 置空。

【代码实现】

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int* tmp=(int*)malloc(sizeof(int)*(m+n));

    int i1 = 0,i2 = 0;
	int i = 0;
	
	//必定有一个数组中的元素全都拷进 tmp 数组了
	while (i1 < m && i2 < n)
	{
		if (nums1[i1] > nums2[i2])
			tmp[i++] = nums2[i2++];
			
		else
			tmp[i++] = nums1[i1++];
	}
	
	//无须关心还有元素没被拷贝的那个数组究竟是 nums1 还是 nums2 ，因为下面的循环必定只进入其中一个
	while (i2 < n)
	{
        tmp[i++] = nums2[i2++];
	}
	
	while (i1 < m)
	{
		tmp[i++] = nums1[i1++];
	}
	
    memcpy(nums1,tmp,sizeof(int)*(m+n)); 
    free(tmp);
    tmp=NULL;
}

这种解法就很优了，时间复杂度是 O(m+n) 。

【类似题目】
合并两个有序链表

更多文章
阶乘后的零（C语言）
调整数组顺序使奇数位于偶数前面（C语言）