合并两个有序数组（详解）
题目：
给你两个按 非递减顺序 排列的整数数组 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;
}
