合并两个有序数组

题目

合并两个有序数组

信息

• 类型：问答
• 难度：⭐

考点

双指针技巧,数组操作,原地合并

快速回答

使用逆向双指针从后向前合并数组：

• 初始化指针：p1指向nums1有效元素末尾，p2指向nums2末尾
• 比较指针值，将较大者放入nums1[p1+p2+1]位置
• 当nums2有剩余元素时直接复制
• 时间复杂度：O(m+n)，空间复杂度：O(1)

问题描述

给定两个按非递减顺序排列的整数数组 nums1 和 nums2，nums1 的空间足够大（长度为 m+n）。合并 nums2 到 nums1 中，使合并后的数组保持非递减顺序。nums1 的前 m 个元素为有效数据，nums2 有 n 个元素。

原理说明

使用逆向双指针避免数据覆盖：

• 传统从前向后合并会覆盖 nums1 原有数据
• 从后向前填充可利用 nums1 尾部空闲空间
• 双指针分别指向两数组有效元素末尾
• 比较指针值，较大者放入合并位置

代码示例

def merge(nums1, m, nums2, n):
    p1, p2 = m - 1, n - 1  # 指向有效元素末尾
    tail = m + n - 1       # 合并位置指针

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1
        tail -= 1

    # 处理 nums2 剩余元素
    nums1[:p2+1] = nums2[:p2+1]

执行步骤

1. 初始化指针：p1 = m-1（nums1末尾），p2 = n-1（nums2末尾）
2. 设置tail = m+n-1（合并位置）
3. 循环比较两指针值，较大者放入tail位置并移动指针
4. 若 nums2 有剩余元素，直接复制到 nums1 头部

最佳实践

• 指针边界：循环条件为 p1≥0 and p2≥0
• 剩余处理：只需处理 nums2 剩余（nums1 剩余已在正确位置）
• 优化技巧：使用切片赋值 nums1[:p2+1] = nums2[:p2+1]

常见错误

• 正向合并：从前向后会导致 nums1 元素被覆盖
• 遗漏剩余：忘记处理 nums2 的剩余元素
• 指针越界：未正确处理指针为负的情况
• 多余操作：对 nums1 剩余元素做额外移动

扩展知识

• 链表合并：双指针同样适用于合并有序链表
• K路归并：可扩展使用最小堆合并K个有序数组
• 稳定性：此算法是稳定的（相等时优先取 nums2 元素）
• 变体问题：合并后去重、合并多个数组等