大家好，我是小卡皮巴拉
文章目录
目录
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
力扣题目： 合并两个有序数组
原题链接：合并两个有序数组
题目描述
给你两个按 非递减顺序 排列的整数数组
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 中。
解题思路
问题理解：
首先，通过阅读题目，我们获得了以下信息：
- 有两个已排序的整数数组
nums1和nums2。nums1的大小为m + n，其中前m个元素是有效的，而后n个元素被初始化为0，用于存放nums2的元素。- 目标是将
nums2合并到nums1中，使得合并后的数组仍然保持非递减顺序，并且结果直接存储在nums1中。算法选择：
归并排序的合并步骤：由于两个数组都是有序的，我们采用归并排序中的合并步骤来合并这两个数组。这种方法从两个数组的末尾开始比较元素，将较大的元素依次放入结果数组的末尾，直到所有元素都被合并。
原地修改：为了满足题目要求，我们直接在
nums1上进行修改，而不是创建一个新的数组来存放结果。这样，我可以利用nums1中已经预留的n个0的空间来存放nums2的元素。索引代替指针：为了简化代码和提高可读性，我们使用下标索引来代替指针来遍历数组。这样，我可以直接使用整数来表示数组中的位置，而不需要处理指针的运算。
具体思路
初始化索引：
index1初始化为m - 1，表示nums1中有效元素的最后一个索引。index2初始化为n - 1，表示nums2中最后一个元素的索引。index初始化为m + n - 1，表示合并后数组的最后一个索引（也即nums1的最后一个索引）。合并两个数组：
- 使用一个循环，当
index1和index2都大于等于 0 时执行。- 在循环内部，比较
nums1[index1]和nums2[index2]的值。
- 如果
nums1[index1]大于或等于nums2[index2]，则将nums1[index1]复制到nums1[index]，并将index1减 1。- 否则，将
nums2[index2]复制到nums1[index]，并将index2减 1。- 在每次循环结束时，将
index减 1，以移动到合并后数组的下一个位置。处理剩余元素：
- 如果
nums2中还有剩余元素（即index2大于等于 0），则直接将nums2中的剩余元素复制到nums1的前面部分。
- 这是因为题目已经说明
nums1后面有足够的空间（n个0），所以不需要担心覆盖nums1中的有效元素。- 注意：在这个问题中，我们不需要处理
nums1的剩余元素，因为题目已经保证了nums1的大小是m + n，且后n个元素是0。所以，当nums2的所有元素都被复制到nums1后，nums1就已经完成了合并。
题目要点
- 理解：两个有序数组，
nums1有预留空间，需原地合并。- 算法：采用归并排序的合并步骤，从后往前合并。
- 索引：设置三个索引指向数组末尾。
- 过程：循环比较，复制较大值，更新索引。
- 剩余：直接复制
nums2的剩余元素到nums1。
作图助解
- 比较
nums1[index1]和nums2[index2]的值。
- 如果
nums1[index1]大于或等于nums2[index2]，则将nums1[index1]复制到nums1[index]，并将index1减 1。- 否则，将
nums2[index2]复制到nums1[index]，并将index2减 1。- 在每次循环结束时，将
index减 1，以移动到合并后数组的下一个位置。
完整代码（C语言）
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { //从后往前遍历数组，找大 int index1 = m - 1; int index2 = n - 1; int index = m + n - 1; while(index1 >= 0 && index2 >= 0) { if(nums1[index1] > nums2[index2]) { nums1[index--] = nums1[index1--]; } else { nums1[index--] = nums2[index2--]; } } //index1已经越界，num2中还有数据没有放到num1中 while(index2 >= 0) { nums1[index--] = nums2[index2--]; } }
兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
