88. 合并两个有序数组

题意

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别

表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情

况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0

，应忽略。nums2 的长度为 n 。

难度

简单

示例

示例 1：

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

输出：[1,2,2,3,5,6]

解释：需要合并 [1,2,3] 和 [2,5,6] 。

合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 >

示例 2：

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

输出：[1]

解释：需要合并 [1] 和 [] 。

合并结果是 [1] 。

示例 3：

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

输出：[1]

解释：需要合并的数组是 [] 和 [1] 。

合并结果是 [1] 。

注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可

以顺利存放到 nums1 中。

分析

本题通常的思路是利用一个长度为 m + n 的辅助数组和两个辅助下标依次比较元素，将

较小的元素放入辅助数组中，并且将对应的下标后移。

最后再将辅助数组填充到 nums1[]即可。题解如下：

class Solution {

public void merge(int[] nums1, int m, int[] nums2, int n) {

// pos 用于记录当前在 temp 数组中的位置

int pos = 0;

// temp 数组用于临时存放合并后的结果

int[] temp = new int[m + n];

// p1 和 p2 分别是 nums1 和 nums2 的指针（下标）

int p1 = 0, p2 = 0;

// 循环条件是 p1 还没遍历完 nums1 或 p2 还没遍历完 nums2

while (p1 < m || p2 < n) {

// 如果 p1 已经遍历完 nums1，则只需将 nums2 的元素复制到 temp

if (p1 == m) {

temp[pos++] = nums2[p2++];

} else {

// 如果 p2 已经遍历完 nums2，则只需将 nums1 的元素复制到 temp

if (p2 == n) {

temp[pos++] = nums1[p1++];

} else {

// 如果 nums1 当前元素 <= nums2 当前元素，则将 nums1 的元素复制到

temp

if (nums1[p1] <= nums2[p2]) {

temp[pos++] = nums1[p1++];

} else {

// 否则，将 nums2 的元素复制到 temp

temp[pos++] = nums2[p2++];

}

}

}

}

// 最后，将合并后的结果从 temp 复制回 nums1

for (int i = 0; i != m + n; ++i) {

nums1[i] = temp[i];

}

}

}

解释：

• 该方法的核心思想是使用双指针（下标），一个指针（下标） p1 遍历 nums1，另一

个指针（下标） p2 遍历 nums2。

• 在每一步，我们比较 nums1[p1] 和 nums2[p2]，并将较小的元素复制到临时数组

temp 中，然后移动相应的指针（下标）。

• 如果其中一个数组已经被完全遍历（即 p1 达到 m 或 p2 达到 n），则只需将另一个

数组的剩余元素复制到 temp。

• 最后，将合并后的结果从 temp 复制回 nums1。

这种方法的时间复杂度是 (O(m+n))，空间复杂度也是 (O(m+n))（由于使用了临时数组

temp）。

来看一下题解效率。

088.%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E

6%95%B0%E7%BB%84-20231010080347.png

但是这样子会多出一个大小为 n+m 的辅助数组。

怎么优化呢？

因为 nums1 在 m 之后的位置（即 m 到 m+n-1），是没有被占用的，所以我们可以利用

这段空间，从后往前依次确定，即从大到小来获取对应的元素即可。

class Solution {

public void merge(int[] nums1, int m, int[] nums2, int n) {

// pos 指向 nums1 的最后一个位置

int pos = m + n - 1;

// 将 m 和 n 减一，让它们直接作为 nums1 和 nums2 的索引

m--;

n--;

// 循环条件是 m 或 n 任一个还没遍历完

while (m >= 0 || n >= 0) {

// 如果 nums1 已经遍历完，只需将 nums2 的元素复制到 nums1

if (m == -1) {

nums1[pos--] = nums2[n--];

} else {

// 如果 nums2 已经遍历完，则 nums1 已在正确位置，只需移动 m

if (n == -1) {

nums1[pos--] = nums1[m--];

} else {

// 比较 nums1 和 nums2 当前元素，将较大的元素放到 nums1 的 pos 位置

if (nums1[m] >= nums2[n]) {

nums1[pos--] = nums1[m--];

} else {

nums1[pos--] = nums2[n--];

}

 }

}

}

}

}

解释：

• 这个方法的核心思想是从两个数组的尾部开始比较，并从 nums1 的尾部开始填充结

果。这样我们可以直接在 nums1 上操作，而不需要额外的存储空间。

• 在每一步，我们比较 nums1[m] 和 nums2[n]，并将较大的元素放在 nums1[pos] 的

位置，然后递减相应的指针（下标）。

• 如果 nums1 的元素都被遍历完了（即 m 为 -1），我们就直接将 nums2 的元素复制

到 nums1。

• 如果 nums2 的元素都被遍历完了（即 n 为 -1），那么 nums1 的元素已经在正确的

位置上，不需要做任何事情。

我们来模拟一下整个过程。

考虑下面的例子:

nums1 = [1,3,5,0,0,0], m=3 和 nums2 = [2,4,6], n=3

这是两个有序数组，我们希望合并 nums2 到 nums1。

我们的指针（下标）分别是：m, n, 和 pos。

初始化状态:

nums1: 1 3 5 0 0 0

index: 0 1 2 3 4 5

nums2: 2 4 6

index: 0 1 2

m=2, n=2, pos=5

开始合并：

1. nums1[m] 是 5, nums2[n] 是 6. 6 更大，所以放入 pos 位置。

nums1: 1 3 5 0 0 6

n--, pos--

2. nums1[m] 是 5, nums2[n] 是 4. 5 更大，所以放入 pos 位置。

nums1: 1 3 5 0 5 6

m--, pos--

3. nums1[m] 是 3, nums2[n] 是 4. 4 更大，所以放入 pos 位置。

nums1: 1 3 5 4 5 6

n--, pos--

4. nums1[m] 是 3, nums2[n] 是 2. 3 更大，所以放入 pos 位置。

nums1: 1 3 3 4 5 6

m--, pos--

5. nums1[m] 是 1, nums2[n] 是 2. 2 更大，所以放入 pos 位置。

nums1: 1 2 3 4 5 6

n--, pos--

6. 最后，我们只剩下 nums1 的第一个元素。但是它已经在正确的位置上，所以不需要做任何事

情。

结束后，nums1 完整地包含了合并后的有序数组。

这种方法的时间复杂度是 (O(m+n))，而空间复杂度是 (O(1))。

088.%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E

6%95%B0%E7%BB%84-20231010080750.png

总结

本题作为学习归并排序的前置题目，非常值得深入研究一下，之后我们学习了归并排序

后，再来看这题，就会触类旁通了。

力扣链接：https://leetcode.cn/problems/merge-sorted-array/