算法 - 合并两个有序数组

Posted on

1. 题目

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终合并后数组不由函数返回，而是存储在数组 nums1 中。nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

示例:

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

2. 解题思路

2.1 为什么不能从前往后双指针？

若从下标 0 开始比较写入 nums1，会覆盖掉 nums1 尚未读取的有效元素。除非先拷贝一份 nums1（额外 O(m) 空间）。

2.2 逆向双指针（从头填充 → 从尾填充，最优）

从后往前填：nums1 的尾部 [m+n-1] 是空的（全是 0 占位），把较大元素放到尾部就不会覆盖未处理数据。

  • 三指针：p1 = m-1、p2 = n-1、tail = m+n-1。

  • 每次比较 nums1[p1] 与 nums2[p2]，把较大者放到 tail，对应指针前移。

  • 当 p1 < 0 时，把 nums2 剩余元素拷进 nums1 头部；当 p2 < 0 时 nums1 剩余部分本就在正确位置，无需处理。

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

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function merge(
    nums1: number[],
    m: number,
    nums2: number[],
    n: number
): void {
    let p1 = m - 1;
    let p2 = n - 1;
    let tail = m + n - 1;

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

    // nums2 还有剩余，必须拷进 nums1 前段
    while (p2 >= 0) {
        nums1[tail--] = nums2[p2--];
    }
    // nums1 有剩余则已在正确位置，无需处理
}

const a = [1, 2, 3, 0, 0, 0];
merge(a, 3, [2, 5, 6], 3);
console.log(a); // [1,2,2,3,5,6]

4. 面试延伸

  • 核心技巧「从后往前」：同适用于「字符串原地替换 / 删除元素」等避免覆盖的场景，是原地合并的通用思路。
  • 对比：合并两个有序链表 用 dummy head 顺序拼接；合并区间（Merge Intervals）则先排序再线性扫描。三者都是「有序归并」家族。
  • 追问：为什么相等时先放 nums1？任意皆可，不影响正确性，只影响稳定性表述。
  • 归并排序 merge 步骤正是此逻辑，可顺势聊排序稳定性。

难度：简单 | LeetCode 88 | 逆向双指针 / 归并