LeetCode 面试题 10.01. 合并排序的数组

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 程序员面试金典（第 6 版） 字节 微软
标签
数组 排序 双指针

题目描述

✅ 面试题 10.01. 合并排序的数组

image-20260928223901763

题意分析

将两个已经按非递减顺序排列的数组合并，并直接写回 A。A 的前 m 项才是有效数据，末尾 n 项是为 B 预留的空间；是否有效由位置决定，不能把数值为 $0$ 的元素一律当作空位。

解法：从后向前合并

核心思路

[!blue]

空余位置位于 A 的尾部，因此可以从结果的最后一位开始填。设 i、j 分别指向两组尚未合并的末尾，k 指向结果中尚未填好的最后一位。由于两组各自有序，未处理元素中的最大值一定是 A[i] 或 B[j]，把较大者写入 A[k] 就能确定这一位。

初始 i = m - 1、j = n - 1、k = m + n - 1。每轮取走一侧的末尾元素，并将写指针左移，因此 k 右侧始终是已经排好的最终后缀，剩余元素只需继续填入前面的空间。

原地写入不会破坏尚未读取的 A：剩余元素数量为 (i + 1) + (j + 1)，正好等于未填位置数量 k + 1，所以始终有 k - i = j + 1。只要 B 还没用完，j >= 0，就有 k > i，写入位置严格在 A 未读前缀右侧。

若 A 先耗尽，就直接把 B 剩余元素依次写入；若 B 先耗尽，此时 j = -1、k = i，A 剩余前缀已经在应有位置，且内部有序，不需要再搬动。因此循环只需以 j >= 0 为条件。

m = 0 时会把 B 全部写入 A；n = 0 时完全不进入循环。两边当前值相等时取哪一边都不影响排序，代码选择 B，另一份相同元素仍保留等待处理。

解题步骤

  1. 初始化三个指针，分别指向 A、B 的有效末尾和结果末尾。
  2. 只要 j >= 0，就继续处理 B 尚未写入的元素。
  3. A 未耗尽且 A[i] > B[j] 时取 A，否则取 B。
  4. 移动被读取一侧的指针，并将 k 左移。

代码实现

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        // 从尾部填最大值；B 写完后，A 的剩余前缀已经就位。
        while (j >= 0) {
            // 先检查 A 是否耗尽，再比较两个候选。
            if (i >= 0 && A[i] > B[j]) {
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }
    }
}

func merge(A []int, m int, B []int, n int) {
    i, j, k := m-1, n-1, m+n-1

    // 从尾部填最大值；B 写完后，A 的剩余前缀已经就位。
    for j >= 0 {
        // 先检查 A 是否耗尽，再比较两个候选。
        if i >= 0 && A[i] > B[j] {
            A[k] = A[i]
            i--
        } else {
            A[k] = B[j]
            j--
        }
        k--
    }
}

复杂度分析

  • 时间复杂度：$O(m+n)$，两个读指针都只向左移动。
  • 空间复杂度：$O(1)$，复用 A 的预留空间。

关键点总结

[!green]

  • 写入方向由预留空间的位置决定：从尾部开始避免覆盖。
  • j >= 0 同时覆盖 A 先耗尽的情况。
  • 相等时取任意一侧都能保持升序，但两个元素最终都要写入。

易错点总结

[!yellow]

  • 把预留的 0 当成数据：A 的读指针从 m-1 开始，而不是 A.length-1。
  • 只循环到任意一侧耗尽：m = 0 时仍要把 B 全部复制到 A。
  • 从前往后直接写入：当需要先取 B 的较小元素时，可能覆盖 A 尚未读取的有效元素。

相似题目

题目 难度 关联与区别
21. 合并两个有序链表 简单 同样合并两个有序序列，本题数组前段可能被写入覆盖，因此常从大到小往后填。
977. 有序数组的平方 简单 同样从两端获取较大候选并从输出末尾写入，避免额外排序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/34153245
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！