LeetCode 88 - 合并两个有序数组

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 尚未排完，直接补充到 nums1while (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++];}// 将结果拷贝回 nums1System.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);// 排序 nums1Arrays.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);}}
}