如何解决leetcode中合并两个有序数组的问题

# 如何解决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))不理想 - 没有利用原始数组已有序的特性

错误方法2：从前向后合并

尝试从数组头部开始比较并插入：

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的末尾。这种方法不需要额外空间，也不会覆盖未处理的元素。

具体步骤

1. 初始化三个指针：

   • p1指向nums1的最后一个有效元素(m-1)
   • p2指向nums2的最后一个元素(n-1)
   • p指向nums1的最后一个位置(m+n-1)

2. 从后向前遍历：

   • 比较nums1[p1]和nums2[p2]
   • 将较大的值放入nums1[p]
   • 对应指针前移

3. 处理剩余元素：

   • 如果nums2还有剩余元素，直接复制到nums1前面
   • nums1的剩余元素已经就位，无需处理

Python实现

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]

复杂度分析

• 时间复杂度：O(m+n)，每个元素只被处理一次
• 空间复杂度：O(1)，只使用了常数个额外变量

边界情况测试

测试用例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]

测试用例2：nums1为空

nums1 = [0]
m = 0
nums2 = [1]
n = 1
merge(nums1, m, nums2, n)
# 输出应为[1]

测试用例3：nums2为空

nums1 = [1]
m = 1
nums2 = []
n = 0
merge(nums1, m, nums2, n)
# 输出应为[1]

测试用例4：包含重复元素

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]

这样只在需要时才执行切片操作。

不同语言实现

Java实现

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);
    }
}

C++实现

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格式编写。