LeetCode88-合并两个有序数组

LeetCode 88 - 合并两个有序数组 是非常基础的数组操作题目，考察双指针、逆序操作和空间优化等技巧。这个问题相当经典，对后续的归并排序、多指针问题、双数组相关问题都有指导意义。以下是详细的解法、模板与变体问题讲解。

---

题目描述

给定你两个有序整数数组 nums1 和 nums2，以及两个非负整数 m 和 n，表示分别代表数组 nums1 和 nums2 中的有效元素个数。

将 nums2 中的所有元素合并到 nums1 中，使数组变为一个有序数组。

你需要在 原地 修改 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]

---

解法及分析 解法 1：双指针，从后向前逆序合并 核心思路

从两个数组的后端（即较大的元素）开始合并：

比较 nums1[m-1] 和 nums2[n-1]，将较大的数填充到 nums1 的最后位置，即索引 m + n - 1。每次填充一个元素，然后移动相应的指针。优化方向：因为 nums1 末尾已经预留了足够空间，所以可以从 后向前 直接覆盖。

特殊情况处理：

如果 nums2 元素还未完全合并（n > 0），需要将剩余的 nums2 元素直接拷贝到 nums1（最终结果仍是有序的）。如果 nums1 已完全扫描完，则只需要简单地覆盖。 模板代码 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1; // 指针指向 nums1 的有效部分末尾 int p2 = n - 1; // 指针指向 nums2 的末尾 int p = m + n - 1; // 指针指向 nums1 的总长度末尾 // 从后向前合并 while (p1 >= 0 && p2 >= 0) { if (nums1[p1] > nums2[p2]) { nums1[p--] = nums1[p1--]; // 将较大值放到 nums1 的末尾 } else { nums1[p--] = nums2[p2--]; } } // 如果 nums2 尚未排完，直接补充到 nums1 while (p2 >= 0) { nums1[p--] = nums2[p2--]; } } } 复杂度分析 时间复杂度: O(m + n)，每个元素只需遍历一次。空间复杂度: O(1)，原地操作，不使用额外空间。适用场景: 空间受限且数组有序。

---

解法 2：双指针，从前向后合并（额外空间） 核心思路

如果允许使用额外空间，可以简单地创建一个临时数组来存储合并结果：

利用两个指针分别扫描 nums1 和 nums2 的有效部分。比较当前指针指向的元素，将较小值存入新的数组。最后将临时数组的元素拷贝回 nums1。

问题：此方法不符合“原地”修改的要求，因此主要用于理解合并逻辑。

模板代码 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] sorted = new int[m + n]; // 新数组 int p1 = 0, p2 = 0, p = 0; // 合并两个数组 while (p1 < m && p2 < n) { if (nums1[p1] <= nums2[p2]) { sorted[p++] = nums1[p1++]; } else { sorted[p++] = nums2[p2++]; } } // 处理剩余元素 while (p1 < m) { sorted[p++] = nums1[p1++]; } while (p2 < n) { sorted[p++] = nums2[p2++]; } // 将结果拷贝回 nums1 System.arraycopy(sorted, 0, nums1, 0, m + n); } } 复杂度分析 时间复杂度: O(m + n)，只需一趟扫描。空间复杂度: O(m + n)，需要额外数组来保存结果。适用场景: 构造新数组后再修改原数组的场景。

---

解法 3：Java 内置排序 核心思路 将 nums2 的有效元素直接拷贝到 nums1 的尾部：nums1[m..m+n] = nums2[0..n] 使用 Java 提供的内置排序方法，将 nums1 排序。

虽然算法简单，但不符合“原地操作”限制，可能会对排序效率和内存有额外要求。

模板代码 import java.util.Arrays; class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { // 将 nums2 拷贝到 nums1 的后面 System.arraycopy(nums2, 0, nums1, m, n); // 排序 nums1 Arrays.sort(nums1); } } 复杂度分析 时间复杂度: O((m + n) log (m + n))，由排序函数的复杂度决定。空间复杂度: O(m + n)，排序中可能需要额外空间。适用场景: 快速验证时使用，但不适合真正工程开发。

---

经典变体问题

---

变体 1：合并两个有序链表

问题背景：

给定两个升序链表，将它们合并为一个升序链表，返回头节点。这个问题与合并数组的逻辑非常相似，但需要操作指针。 模板代码 class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); // 哑节点 ListNode current = dummy; // 合并链表 while (l1 != null && l2 != null) { if (l1.val <= l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } // 连接剩余部分 current.next = (l1 != null) ? l1 : l2; return dummy.next; } }

---

变体 2：寻找两个有序数组的中位数

问题背景：

输入是两个升序数组，找到它们合并后的中位数。与本题不同，此处需要合并逻辑在不显式合并的情况下完成。 解决方法: 可使用双指针法： class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int left = (m + n + 1) / 2; int right = (m + n + 2) / 2; return (findK(nums1, 0, nums2, 0, left) + findK(nums1, 0, nums2, 0, right)) / 2.0; } private int findK(int[] nums1, int i, int[] nums2, int j, int k) { if (i >= nums1.length) return nums2[j + k - 1]; if (j >= nums2.length) return nums1[i + k - 1]; if (k == 1) return Math.min(nums1[i], nums2[j]); int mid1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE; int mid2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE; if (mid1 < mid2) { return findK(nums1, i + k / 2, nums2, j, k - k / 2); } else { return findK(nums1, i, nums2, j + k / 2, k - k / 2); } } }

---

快速 AC 总结 双指针法是首选： 从后向前合并（逆序操作）是最优解，时间 O(m + n)，空间 O(1)。 理解链表和数组问题的共同逻辑： 合并逻辑、双指针技巧可以直接应用在链表问题或排序问题上。 注意特例： 例如其中一个数组为空时，不需要额外逻辑处理，直接完成即可（已覆盖于模板代码中）。 灵活应对变体问题： 比如排序、寻找中位数问题，都可以通过拆解问题或类似合并的思想解决。

通过掌握双指针技巧和其相关变体题目，可以轻松快速解决这类问题！