LeetCode 88. 合并两个有序数组

约 4 分钟
文章信息 25 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 商汤 虾皮 哔哩哔哩 贝壳 面试经典 150 题
标签
数组 排序 双指针 双指针经典题
目录

题目描述

✅ 88. 合并两个有序数组

image-20230304203633160

image-20230304203641480

题意分析

给定两个非递减排列的整数数组 nums1 和 nums2，它们的有效元素个数分别是 m 和 n。要求把两者合并成一个非递减序列，而且结果必须存放进 nums1，函数本身不返回任何值——判题看的是调用结束后 nums1 里的内容。

本题真正特殊的地方在于 nums1 的长度不是 m，而是 m + n：前 m 个位置放着有效数据，后面恰好预留了 n 个空位。这些尾部位置在示例里通常显示成 0，但它们是占位符，不是数据：既不参与比较，也不该出现在答案里。相对地，nums2 的长度就是 n，没有任何多余空位。所以「nums1 里有几个 0」这件事完全不能作为判断依据，能用的只有参数 m 和 n。

「预留恰好 n 个空位」是全题的关键信号，它同时说明了两件事。第一，出题人不希望你另开一个数组再返回，答案只能原地写在 nums1 上。第二，也是更要紧的一点：nums1 的容量正好等于最终答案的长度，因此如果从尾部往前填，写入位置的推进速度和读取位置的消耗速度是匹配的——每写一格就消耗一个待合并元素，写指针永远不会追上还没读取的有效数据。反过来，如果从头往前填，nums1 前半段既是读取区又是写入区，两者会撞在一起。方向的选择不是风格问题，而是这道题唯一能原地做对的前提。

边界情况有两个。m = 0 时 nums1 没有有效数据（此时它的长度就是 n，整个数组都是预留区），答案就是 nums2 的全部内容；n = 0 时 nums2 为空，nums1 原封不动就是答案，一个字都不用改。这两种情况都要求实现里不能无条件地去访问 nums1[m - 1] 或 nums2[n - 1]，否则会立刻越界。

解法：从后往前双指针

核心思路

nums1 尾部有足够空间。分别从两个有效区间的末尾取较大值，写入 nums1 末尾，这样不会覆盖尚未比较的元素。只需保证 nums2 全部写入；若 nums1 有剩余，它们已经在正确位置。

解题步骤

  1. 令 i = m - 1、j = n - 1，分别指向两个数组的有效末尾；k = m + n - 1 指向写入位置。
  2. 当 j >= 0 时，比较两个指针指向的元素，把较大值写入 nums1[k]。
  3. 左移被选中的读指针和写指针 k。
  4. j < 0 时结束；nums1 的剩余元素无需移动。

代码实现

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

        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

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

    for j >= 0 {
        if i >= 0 && nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }
}

复杂度分析

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

关键点总结

  • 从后往前放较大值，避免覆盖 nums1 中尚未读取的元素。
  • 判断条件先检查 i >= 0，再访问 nums1[i]。
  • 循环只需保证 nums2 耗尽，nums1 的剩余部分天然有序且位置正确。

易错点总结

  • 从前往后原地合并，会覆盖 nums1 的未读元素。
  • 把 i 初始化为 nums1.length - 1，会把尾部占位符当成有效数据；应使用 m - 1。
  • 主循环只比较两边都有元素的情况，却忘记继续写入 nums2 的剩余元素。
  • i < 0 后仍访问 nums1[i]，会导致数组越界。

相似题目

题目 难度 考察点
面试题 10.01. 合并排序的数组 简单 与本题几乎完全相同，只是参数命名不同，逆向双指针可以原样套用
21. 合并两个有序链表 简单 载体换成链表，靠改 next 指针接节点，不存在覆盖问题也无法反向遍历
23. 合并 K 个升序链表 困难 从两路扩展到 K 路，选最小值需要优先队列或分治，而非一次比较两个候选
977. 有序数组的平方 简单 只有一个数组，但最大值出现在两端而非一端，要从两头向中间取并逆序填结果
283. 移动零 简单 原地重排单个数组且要保序，读写指针都从前往后，因为写指针天然落后于读指针
27. 移除元素 简单 原地删除而非合并，只需一个写指针跟在读指针后面收集保留元素，不涉及有序性
26. 删除有序数组中的重复项 简单 同样利用输入有序，但目标是压缩去重、结果变短，判断依据是与前一个保留值比较