088.合并两个有序数组

作者：沉默王二
发布时间：2023-10-10T08:14:54.899+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你两个按 非递减顺序 排列的整数数组 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] 。

示例 3：

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

解释：需要合并的数组是 [] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

分析

本题通常的思路是利用一个长度为m + n的辅助数组和两个辅助下标依次比较元素，将较小的元素放入辅助数组中，并且将对应的下标后移。

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

class Solution {

        // 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）。

来看一下题解效率。

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

怎么优化呢？

因为nums1在m之后的位置（即m到m+n-1），是没有被占用的，所以我们可以利用这段空间，从后往前依次确定，即从大到小来获取对应的元素即可。

class Solution {

        // 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

nums2:  2  4  6index:  0  1  2
m=2, n=2, pos=5

开始合并：

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

n--, pos--
2. nums1[m] 是 5, nums2[n] 是 4. 5 更大，所以放入 pos 位置。nums1:  1  3  5  0  5  6m--, pos--
3. nums1[m] 是 3, nums2[n] 是 4. 4 更大，所以放入 pos 位置。nums1:  1  3  5  4  5  6n--, pos--
4. nums1[m] 是 3, nums2[n] 是 2. 3 更大，所以放入 pos 位置。nums1:  1  3  3  4  5  6m--, pos--
5. nums1[m] 是 1, nums2[n] 是 2. 2 更大，所以放入 pos 位置。nums1:  1  2  3  4  5  6n--, pos--
6. 最后，我们只剩下 nums1 的第一个元素。但是它已经在正确的位置上，所以不需要做任何事情。

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

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

总结

本题作为学习归并排序的前置题目，非常值得深入研究一下，之后我们学习了归并排序后，再来看这题，就会触类旁通了。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你两个按 非递减顺序 排列的整数数组 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] 。

示例 3：

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

解释：需要合并的数组是 [] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

分析

本题通常的思路是利用一个长度为m + n的辅助数组和两个辅助下标依次比较元素，将较小的元素放入辅助数组中，并且将对应的下标后移。

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

class Solution {

        // 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）。

来看一下题解效率。

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

怎么优化呢？

因为nums1在m之后的位置（即m到m+n-1），是没有被占用的，所以我们可以利用这段空间，从后往前依次确定，即从大到小来获取对应的元素即可。

class Solution {

        // 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

nums2:  2  4  6index:  0  1  2
m=2, n=2, pos=5

开始合并：

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

n--, pos--
2. nums1[m] 是 5, nums2[n] 是 4. 5 更大，所以放入 pos 位置。nums1:  1  3  5  0  5  6m--, pos--
3. nums1[m] 是 3, nums2[n] 是 4. 4 更大，所以放入 pos 位置。nums1:  1  3  5  4  5  6n--, pos--
4. nums1[m] 是 3, nums2[n] 是 2. 3 更大，所以放入 pos 位置。nums1:  1  3  3  4  5  6m--, pos--
5. nums1[m] 是 1, nums2[n] 是 2. 2 更大，所以放入 pos 位置。nums1:  1  2  3  4  5  6n--, pos--
6. 最后，我们只剩下 nums1 的第一个元素。但是它已经在正确的位置上，所以不需要做任何事情。

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

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

总结

本题作为学习归并排序的前置题目，非常值得深入研究一下，之后我们学习了归并排序后，再来看这题，就会触类旁通了。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给你两个按 非递减顺序 排列的整数数组 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] 。

示例 3：

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

解释：需要合并的数组是 [] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

分析

本题通常的思路是利用一个长度为m + n的辅助数组和两个辅助下标依次比较元素，将较小的元素放入辅助数组中，并且将对应的下标后移。

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

class Solution {

        // 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）。

来看一下题解效率。

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

怎么优化呢？

因为nums1在m之后的位置（即m到m+n-1），是没有被占用的，所以我们可以利用这段空间，从后往前依次确定，即从大到小来获取对应的元素即可。

class Solution {

        // 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

nums2:  2  4  6index:  0  1  2
m=2, n=2, pos=5

开始合并：

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

n--, pos--
2. nums1[m] 是 5, nums2[n] 是 4. 5 更大，所以放入 pos 位置。nums1:  1  3  5  0  5  6m--, pos--
3. nums1[m] 是 3, nums2[n] 是 4. 4 更大，所以放入 pos 位置。nums1:  1  3  5  4  5  6n--, pos--
4. nums1[m] 是 3, nums2[n] 是 2. 3 更大，所以放入 pos 位置。nums1:  1  3  3  4  5  6m--, pos--
5. nums1[m] 是 1, nums2[n] 是 2. 2 更大，所以放入 pos 位置。nums1:  1  2  3  4  5  6n--, pos--
6. 最后，我们只剩下 nums1 的第一个元素。但是它已经在正确的位置上，所以不需要做任何事情。

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

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

总结

本题作为学习归并排序的前置题目，非常值得深入研究一下，之后我们学习了归并排序后，再来看这题，就会触类旁通了。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412