# 如何解决LeetCode中合并两个有序数组的问题 ## 问题描述 LeetCode第88题"合并两个有序数组"(Merge Sorted Array)要求我们将两个有序整数数组合并到第一个数组中，并保持合并后的数组仍然有序。具体描述如下： 给定两个按非递减顺序排列的整数数组`nums1`和`nums2`，以及两个整数`m`和`n`，分别表示`nums1`和`nums2`中的元素数量。需要将`nums2`合并到`nums1`中，使合并后的数组同样按非递减顺序排列。 注意： - `nums1`的长度为`m + n`，其中前`m`个元素表示应合并的元素，后`n`个元素为0，应被忽略 - `nums2`的长度为`n` ## 初始理解问题 首先我们需要明确几个关键点： 1. 原地修改：必须直接修改`nums1`而不是返回新数组 2. 空间利用：`nums1`尾部有足够的空间（n个0）来容纳`nums2`的元素 3. 有序合并：最终结果必须保持非递减顺序 ## 常见错误思路 ### 错误方法1：先合并后排序 ```python def merge(nums1, m, nums2, n): nums1[m:] = nums2 nums1.sort() 虽然简单，但： - 时间复杂度O((m+n)log(m+n))不理想 - 没有利用原始数组已有序的特性
尝试从数组头部开始比较并插入：
def merge(nums1, m, nums2, n): i = j = 0 while j < n: if i >= m or nums2[j] < nums1[i]: nums1.insert(i, nums2[j]) j += 1 m += 1 i += 1 问题在于： - insert操作导致O(n)时间复杂度 - 频繁移动数组元素效率低下 - 实际题目中nums1是固定长度列表，无法使用insert
利用nums1后半部分的空闲空间，从两个数组的末尾开始比较，将较大的元素放到nums1的末尾。这种方法不需要额外空间，也不会覆盖未处理的元素。
初始化三个指针：
p1指向nums1的最后一个有效元素(m-1)p2指向nums2的最后一个元素(n-1)p指向nums1的最后一个位置(m+n-1)从后向前遍历：
nums1[p1]和nums2[p2]nums1[p]处理剩余元素：
nums2还有剩余元素，直接复制到nums1前面nums1的剩余元素已经就位，无需处理def merge(nums1, m, nums2, n): p1, p2, p = m-1, n-1, m+n-1 while p1 >= 0 and p2 >= 0: if nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 # 处理nums2剩余元素 nums1[:p2+1] = nums2[:p2+1] nums1 = [1,2,3,0,0,0] m = 3 nums2 = [2,5,6] n = 3 merge(nums1, m, nums2, n) # 输出应为[1,2,2,3,5,6] nums1 = [0] m = 0 nums2 = [1] n = 1 merge(nums1, m, nums2, n) # 输出应为[1] nums1 = [1] m = 1 nums2 = [] n = 0 merge(nums1, m, nums2, n) # 输出应为[1] nums1 = [1,2,2,0,0,0] m = 3 nums2 = [2,3,3] n = 3 merge(nums1, m, nums2, n) # 输出应为[1,2,2,2,3,3] 可以提前终止循环当p2 < 0时：
while p2 >= 0: if p1 >= 0 and nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 这样当nums2处理完后立即结束，避免不必要的比较。
对于Python，最后的剩余元素处理可以改为：
if p2 >= 0: nums1[:p2+1] = nums2[:p2+1] 这样只在需要时才执行切片操作。
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1, p2 = n - 1, p = m + n - 1; while (p1 >= 0 && p2 >= 0) { nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--]; } System.arraycopy(nums2, 0, nums1, 0, p2 + 1); } } class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = m - 1, p2 = n - 1, p = m + n - 1; while (p1 >= 0 && p2 >= 0) { nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--]; } while (p2 >= 0) { nums1[p--] = nums2[p2--]; } } }; 合并有序数组的算法在以下场景中有实际应用： 1. 数据库系统中的多路归并 2. 归并排序中的合并步骤 3. 版本控制系统的文件合并 4. 大数据处理中的外部排序
解决LeetCode 88题的关键在于： 1. 利用数组已有序的特性 2. 从后向前处理避免元素覆盖 3. 合理使用指针减少空间复杂度
该问题虽然简单，但很好地考察了对数组操作、指针运用和边界条件的处理能力。掌握这种从后向前的双指针技巧，可以解决许多类似的数组合并问题。 “`
这篇文章共计约1900字，包含了问题分析、错误示范、正确解法、复杂度分析、测试用例、优化思路、多语言实现和实际应用等内容，采用Markdown格式编写。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
