88. 合并两个有序数组（Merge Sorted Array）

频次 ★★★ · 难度 🟢 · 高频：全厂

题目

给定两个有序数组 nums1 和 nums2，将 nums2 合并到 nums1 中。nums1 初始长度为 m，但有足够空间（总长度 m+n）容纳 nums2 的 n 个元素。

示例：

输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

思路

从后往前合并，避免覆盖 nums1 的原始数据：

• 三个指针：p1 指向 nums1 末尾有效元素，p2 指向 nums2 末尾，p 指向合并后末尾位置
• 比较 nums1[p1] 和 nums2[p2]，较大者放到 nums1[p]
• 如果 nums2 还有剩余，直接拷贝（nums1 已空时无需处理，元素已在正确位置）

代码

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) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p--] = nums1[p1--];
        } else {
            nums1[p--] = nums2[p2--];
        }
    }
    // nums2 剩余元素拷贝（nums1 剩余时已在正确位置）
    while (p2 >= 0) {
        nums1[p--] = nums2[p2--];
    }
}

复杂度

• 时间：O(m + n) — 每个元素最多访问一次
• 空间：O(1) — 只用指针变量

边界条件

• nums2 为空（n == 0）：两个 while 循环都不执行或立刻退出，nums1 保持不变，正确。
• nums1 有效部分为空（m == 0）：第一个循环因 p1 < 0 立即退出，第二个循环把 nums2 全部拷贝过去，正确。
• nums1、nums2 有相同值：nums1[p1] > nums2[p2] 用的是严格大于，相等时优先放 nums2 的值，不影响结果正确性（相同值谁在前都一样）。

变式

• 如果从前往后合并：需要先把 nums1 的前 m 个元素挪到一个临时数组，否则会覆盖还没处理的原始数据——这也是为什么标准解法要”从后往前”。
• 合并到一个新数组而不是原地：直接用标准归并两个有序数组的写法即可，不用担心覆盖问题，双指针从头开始即可。

易错点

• 从前往后合并是最容易掉进的坑：nums1 前 m 个是有效数据，从前往后写会覆盖还没比较过的元素，必须从后往前写，利用 nums1 后面本来就空着的位置。
• 循环结束条件是 p1 >= 0 && p2 >= 0，退出后如果 p2 还有剩余必须继续拷贝；p1 有剩余则不需要额外处理，因为它已经在正确位置上了——漏掉 p2 剩余拷贝是最常见的 bug。

面试追问

• 为什么不直接把两个数组拼起来再排序？ 拼接排序是 O((m+n) log(m+n))，而两个数组本身已经有序，归并只需要 O(m+n)，面试官通常会追问这个复杂度差异。
• 如果 nums1 没有多余空间存放 nums2 呢？ 那就不能原地合并，只能额外开一个大小为 m+n 的数组做标准归并，本质上是同一个算法，只是空间复杂度从 O(1) 变成 O(m+n)。

关联题

• 同套路：21. 合并两个有序链表 —— 链表版；23. 合并K个排序链表 —— K 路版
• 易混：数组必须从后往前写避免覆盖，链表改指针则无此约束——被追问”为什么倒着来”要能答出这层
• 知识点：本题就是归并排序的 merge 步骤，见数据结构与算法