MUYI · 后端工程师的生产级知识体系

Appearance

合并两个有序数组 ​

一、题目（LeetCode 88 · 简单 · Hot100） ​

给定两个非递减数组 nums1 与 nums2，把 nums2 合并进 nums1。nums1 长度为 m + n：前 m 个是有效元素，后 n 个是 0 占位（正好留给 nums2）。nums2 长度为 n。原地合并，使 nums1 整体非递减，不返回新数组。

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

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]

二、思路演进 ​

2.1 起点顺推：正向归并，方向对了但位置不对 ​

归并的自然直觉是从小到大：双指针各指数组头部，每轮取较小者写入。问题出在写进谁——正向写 nums1 时，头部是 nums1 自己还没被取走的元素，写入会把它覆盖掉。两条出路：一是开一个辅助数组装结果再整体拷回（额外 O(m+n) 空间）。二是逐个插入 nums2 的元素、把 nums1 后段整体搬移腾位（每次插入搬一段，最坏退化到 O(n·m)）。思路是 O(m+n) 的，代价被"写方向"吃掉了。

2.2 关键洞察：nums1 尾部是预留空位，从后往前填大数 ​

换个方向一切通顺：从最终数组的最后一格往前写，每轮取两数组当前未归位的较大者。为什么可行：nums1 的尾部 n 格本来就是空位，写它不覆盖任何有效数据。而"较大者"放进尾部后不可能再被越过——剩下要写的都 ≤ 它。写位置 tail 与两指针同步前移，无辅助数组、无搬移。这就是"遍历方向服从数据布局"的典型例子，与链表版的对照见第六节。

三、复杂度分析 ​

  • 时间 O(m + n)：每个元素恰好被写入一次，指针单调前移。
  • 空间 O(1)：原地，只用三个下标变量。

四、代码 ​

java
package org.example;

import java.util.Arrays;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/23（主推版；2023 原稿对照见文末）
 */
public class LeetCode_88 {

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        merge(nums1, 3, new int[]{2, 5, 6}, 3);
        System.out.println(Arrays.toString(nums1));    // [1, 2, 2, 3, 5, 6]

        int[] nums3 = {0};
        merge(nums3, 0, new int[]{1}, 1);
        System.out.println(Arrays.toString(nums3));    // [1]
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;            // nums1 有效段的尾指针
        int j = n - 1;            // nums2 的尾指针
        int tail = m + n - 1;     // 写入位置：最终数组的最后一格，只减不增
        while (j >= 0) {          // nums2 全部归位即可停：nums1 剩余段本来就在最终位置
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[tail--] = nums1[i--];
            } else {
                nums1[tail--] = nums2[j--];
            }
        }
    }
}

五、坑点 ​

  • 从后往前，不是从小到大：正向写 nums1 必然覆盖未取出的元素。这是本题的第一反应陷阱（2.1 的两条出路都是为它买单）。
  • m、n 先减一再用：i = m - 1、j = n - 1 指向的是"最后一个有效元素"，不是长度本身；m = 0 时 i 为 -1，循环里靠 i >= 0 守护。
  • nums2 先耗尽即可停：循环条件只看 j >= 0。nums1 的剩余段已经在最终位置，再多拷一遍虽不错但白做（原稿 merge4 的收尾 arraycopy 就省在这一点上）。n = 0 时循环一次都不进，nums1 原样就是答案。
  • 相等时取哪边都对：nums1[i] > nums2[j] 用严格大于，相等时走 else 取 nums2——数值数组没有稳定性负担，但两边必须写一致。
  • tail 初值是 m + n - 1：写成 n - 1 或 m - 1 都会把前几个大数盖到有效段上，第一轮输出就能看出错。

六、变形追问 ​

  • 变体一（合并 K 个有序数组，一句话思路）：K 路各持一个指针，小顶堆维护"K 个当前头部"的最小值。每轮弹一个写一个，复杂度 O(N log K)，N 为总元素数。或两两分治归并，与归并排序同构。
  • 变体二（合并两个有序链表，LeetCode 21，Hot100）：同一思想的链表版，方向却相反。链表从前往后（插入 O(1)，没有挪动成本），数组从后往前（尾部有预留空间）。方向由存储结构决定，展开见 合并两个有序链表。

对照解法：2023 原稿（正向双指针 + 辅助数组） ​

原稿（LeetCode_1，2023-12-23，含 merge~merge4 四版演进）的 merge2 是 2.1"辅助数组"路线的代表。保留一版作对照——正确但多付了一份 O(m+n) 空间与一次整体拷回：

java
/**
 * @date 2023/12/23 14:16（原稿 merge2，正向双指针 + 辅助数组）
 */
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
    // 初始化临时数组三
    int[] nums3 = new int[m + n];

    if (m == 0) {
        System.arraycopy(nums2, 0, nums3, 0, n);
    } else if (n == 0) {
        System.arraycopy(nums1, 0, nums3, 0, m);
    } else {
        // 双指针遍历数组一和数组二，将结果每次比较后小的元素插入到数组三中
        int pointer_1 = 0;
        int pointer_2 = 0;
        int pointer_3 = 0;
        do {
            // 比较并赋值
            int data_1 = nums1[pointer_1];
            int data_2 = nums2[pointer_2];
            if (data_2 <= data_1) {
                nums3[pointer_3] = data_2;
                pointer_2++;
            } else {
                nums3[pointer_3] = data_1;
                pointer_1++;
            }

            // 将数组三的指针移动到下一次待赋值的下标
            pointer_3++;
        } while (pointer_2 < n && pointer_1 < m);

        if (pointer_1 >= m) {
            System.arraycopy(nums2, pointer_2, nums3, pointer_3, n - pointer_2);
        }
        if (pointer_2 >= n) {
            System.arraycopy(nums1, pointer_1, nums3, pointer_3, m - pointer_1);
        }
    }

    System.arraycopy(nums3, 0, nums1, 0, m + n);
}

2026-10 重写为 E 轨六段体例（原稿 2023-12-23，纯代码残稿）。