面试经典150题[001]：合并两个有序数组（LeetCode 88）

合并两个有序数组（LeetCode 88）

https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

1. 题目背景

你有两个已经排好序的数组：

• nums1：前面是有效数字，后面是空位（0 占位），用来放另一个数组的元素。
• nums2：完整的、也是排好序的数组。

目标是把 nums2 的元素合并到 nums1 中，并且 最终 nums1 还是升序。

例子

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3

前 3 个数 [1, 2, 3] 是有效的，后面 3 个 0 是空位。
要把 [2, 5, 6] 填进去，最终得到：

[1, 2, 2, 3, 5, 6]

2. 常见但低效的解法

有些同学会这样做：

1. 把 nums2 直接加到 nums1 的后面。
2. 调用 .sort() 排序。

虽然能跑通，但时间复杂度是 O((m+n) log(m+n))，不够快。
面试官通常会追问：能不能 O(m+n) 时间完成？

3. 高效解法——从尾巴开始合并

关键思路

因为两个数组都是升序的，我们可以用 双指针 从 尾部 往前填空位。

这样有两个好处：

• 不会覆盖掉还没处理的数字。
• 不需要移动数组中已有的元素。

三个指针的定义

• p1 = m - 1 → 指向 nums1 有效部分的最后一个元素。
• p2 = n - 1 → 指向 nums2 的最后一个元素。
• p = m + n - 1 → 指向 nums1 的最后一个位置（空位）。

合并过程（例子推演）

以 nums1 = [1,2,3,0,0,0] 和 nums2 = [2,5,6] 为例：

4. 为什么要 p1 >= 0 判断？

如果 nums1 的有效部分先用完（p1 < 0），那就不能再访问 nums1[p1]，否则会越界（尤其在 C++ 里直接崩溃）。
所以我们要保护一下：

if p1 >= 0 and nums1[p1] > nums2[p2]:
    ...
else:
    ...

5. Python 实现

def merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    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

6. C++ 实现

#include <vector>
using namespace std;

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int p = m + n - 1;

    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

7. 小结

口诀：

三指针，从尾走，谁大放谁，谁没了放另一个。

• 从尾往前填空位，不会破坏还没处理的数字。
• 用 p1 >= 0 防止越界。
• 最终复杂度 O(m+n)，空间 O(1)。