合并两个有序数组（详解）

合并两个有序数组

题目：

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

对于这个问题，我们先来看一个之前我们熟悉的思路

思路1：

我们把nums2数组的元素放到 nums1数组里面去然后再用冒泡排序去对nums1进行排序。

这个思路是可以的但是我们知道冒泡排序的由于有两个for循环嵌套，效率没有那么理想，因此我们这个时候就可以考虑另外一个思路

思路2：

我们可以采用三指针法。创建三个指针l1，l2，l3
我们让第二个数组的数据合并到第一个数组中
让l1，l2，l3分别指向第一个有序数组的最后一个有效数字，第二个有序数组的最后一个有效数字，第一个数组的最后一个有效空间
让l1和l2指向的数字去进行对比，l1大就放到l3去，并让l3-- ，l1–。l2大就让l2放到l3中去，并让l3–，l2–。
一直对比直至，让l1或者l2 出了边界

如图所示：

对于这个题目来说，我们需要分类讨论

第一种情况：（l1先出了边界）

l1 和 l2 指向的数字进行比较，谁大谁就放到l3

并且和l3一起–

但是由于l1先出了循环导致nums2 还有数字没有存放到l1中

如图所示：

因此我们还需要将剩余的数字放到nums1中

我们通过循环去把nums2中的数据去放到l3中

每放一个数字 l2和l3都要–

第二种情况：（l2先出边界）

这个情况是不需要做额外处理的，因为两个数组本身就是有序的，如果l2的数据已经全部排序到l1中，那么此时l1就是有序的

如图所示：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// 创建三个变量分别指向 l1 和 l2 的最后一个有效数字，以及l1的最后一个空间int l1,l2,l3;l1 = m - 1;l2 = n - 1;l3 = n + m - 1;while(l1 >= 0 && l2 >= 0){if(nums1[l1] < nums2[l2]){nums1[l3] = nums2[l2];l2--;l3--;}else{nums1[l3] = nums1[l1];l1--;l3--;}}// 走到这里 不是l1出边界 就是l2 出边界  但是我们只需要对l1出边界的情况处理// 因为l1出边界就代表l2还有数据没有合并到l1  // 如果是l2出边界就代表此时l1的数据已经是有序得了  因为原本两个数组就是有序的while(l2>=0){nums1[l3] = nums2[l2];l3--;l2--;}
}

优化一小下：

void merge(int* nums1, int m, int* nums2, int n)
{// 首先我们创建三个int变量作为下标  // l1指向nums1的最后一个数字 l2指向nums2的最后一个数字 l3指向nums1的最后一个空间int l1, l2, l3;l1 = m - 1;l2 = n - 1;l3 = m + n - 1;while (l1 >= 0 && l2 >= 0) // 只要l1 和 l2 < 0 就要退出循环 单独处理{// 判断l1 和 l2 指向的数字谁大 谁大 就放到l3处if (nums1[l1] > nums2[l2]){nums1[l3--] = nums1[l1--]; // 别忘了--}else // 这里说明l2大{nums1[l3--] = nums2[l2--];}}// 走到这里说明 要不就排好了 要不就是l2 或者 l1 出了边界// 而我们只需要对l1出边界的情况做好处理  （因为l1和l2 不会同时出边界 如果l2出了边界就说明排好了）// l1出边界 就说明 nums2还有数字没有放到nums1中 while (l2 >= 0){nums1[l3--] = nums2[l2--];}
}int main()
{int nums1[] = { 1 };int nums2[] = {0};merge(nums1, 1, nums2, 0);for (int i = 0; i < 1; i++){printf("%d ", nums1[i]); // 1}return 0;
}