LeetCode中如何合并两个有序数组

# LeetCode中如何合并两个有序数组

## 问题描述

LeetCode第88题"合并两个有序数组"（Merge Sorted Array）是算法学习中的经典问题。题目要求如下：

给定两个按非递减顺序排列的整数数组`nums1`和`nums2`，以及两个整数`m`和`n`，分别表示`nums1`和`nums2`中的元素数目。要求将`nums2`合并到`nums1`中，使合并后的数组同样按非递减顺序排列。

注意：
- `nums1`的长度为`m + n`，其中前`m`个元素表示应合并的元素，后`n`个元素为0，应被忽略
- `nums2`的长度为`n`

示例：
```python
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

解题思路分析

方法一：直接合并后排序（不推荐）

最直观的方法是直接将nums2放入nums1的尾部，然后对整个数组进行排序。

def merge(nums1, m, nums2, n):
    nums1[m:] = nums2
    nums1.sort()

时间复杂度：O((m+n)log(m+n))
空间复杂度：O(1)

虽然简单，但这种方法没有利用数组已有序的特性，效率不高。

方法二：双指针法（从前往后）

利用两个指针分别指向nums1和nums2的开头，比较两个指针所指元素，将较小的放入新数组。

def merge(nums1, m, nums2, n):
    sorted = []
    p1, p2 = 0, 0
    while p1 < m or p2 < n:
        if p1 == m:
            sorted.append(nums2[p2])
            p2 += 1
        elif p2 == n:
            sorted.append(nums1[p1])
            p1 += 1
        elif nums1[p1] < nums2[p2]:
            sorted.append(nums1[p1])
            p1 += 1
        else:
            sorted.append(nums2[p2])
            p2 += 1
    nums1[:] = sorted

时间复杂度：O(m+n)
空间复杂度：O(m+n)

这种方法需要额外的空间存储排序结果，不符合题目要求的原地修改。

方法三：逆向双指针法（最优解）

从两个数组的末尾开始比较，将较大的元素放入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
    nums1[:p2+1] = nums2[:p2+1]

时间复杂度：O(m+n)
空间复杂度：O(1)

代码实现详解

以最优的逆向双指针法为例，详细解析实现过程：

1. 初始化指针：

   • p1指向nums1的最后一个有效元素（索引m-1）
   • p2指向nums2的最后一个元素（索引n-1）
   • p指向nums1的末尾（索引m+n-1）

2. 比较和填充：

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

3. 处理剩余元素：

   • 如果nums2还有剩余元素（p2 >= 0），直接复制到nums1开头

边界情况处理

1. nums1为空：直接将nums2全部复制到nums1
2. nums2为空：无需任何操作
3. 所有nums1元素大于nums2：nums2元素会先被处理完
4. 所有nums2元素大于nums1：nums1元素会先被处理完

复杂度分析

实际应用场景

合并有序数组的思想广泛应用于： 1. 数据库的归并排序 2. 大数据处理中的外排序 3. 分布式系统中的有序结果合并 4. 版本控制系统中的变更合并

变种问题

1. 合并K个有序数组：使用优先队列（堆）来优化
2. 合并两个有序链表：LeetCode第21题
3. 合并区间：LeetCode第56题

总结

合并两个有序数组问题展示了如何利用双指针技巧高效处理有序数据。逆向双指针法通过从后向前填充，实现了O(1)空间复杂度的原地修改，是最优解决方案。掌握这种方法对理解更复杂的归并类算法有重要意义。

参考代码（Python）

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m-1, n-1
        for p in range(m+n-1, -1, -1):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1

扩展思考

1. 如果要求保持稳定性（相等元素的原始顺序）该如何修改？
2. 如果数组是降序排列的，算法需要如何调整？
3. 如何用递归方式实现这个算法？

通过这些问题可以进一步加深对合并算法的理解。 “`

注：本文约1500字，详细介绍了LeetCode合并两个有序数组问题的多种解法，重点分析了最优解决方案的实现细节和复杂度，并提供了相关扩展思考。