LC 88. 合并两个有序数组

题目描述

这是 LeetCode 上的 88. 合并两个有序数组 ，难度为简单。

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

1
2
3

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

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

示例 2：

1
2
3

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

输出：[1]

提示：

$nums1.length = m + n$
$nums2.length == n$
$0 <= m, n <= 200$
$1 <= m + n <= 200$
$-10^9 <= nums1[i], nums2[i] <= 10^9$

模拟

最简单的做法，我们可以将 $nums2$ 的内容先搬到 $nums1$ 去，再对 $nums1$ 进行排序。

Java 代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }
}

C++ 代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        copy(nums2.begin(), nums2.end(), nums1.begin() + m);
        sort(nums1.begin(), nums1.end());
    }
};

Python 代码：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:m+n] = nums2
        nums1.sort()

TypeScript 代码：

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    nums1.splice(m, n, ...nums2);
    nums1.sort((a, b) => a - b);
};

时间复杂度：$O((m + n)\log{(m + n)})$
空间复杂度：$O(1)$

PS. Java 中的 sort 排序是一个综合排序。包含插入/双轴快排/归并/timsort，这里假定 Arrays.sort 使用的是「双轴快排」，并忽略递归带来的空间开销。

双指针 - 额外空间

上述方法，粗暴地将两个数组结合，再对结果进行排序，没有很好利用俩数组本身有序的特性。

一个容易想到的，可以避免对结果排序的做法是：创建一个和 $nums1$ 等长的数组 $arr$，使用双指针将 $num1$ 和 $nums2$ 的数据迁移到 $arr$，最后再将 $arr$ 复制到 $nums1$ 中。

Java 代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int total = m + n, idx = 0;
        int[] arr = new int[total];
        for (int i = 0, j = 0; i < m || j < n;) {
            if (i < m && j < n) {
                arr[idx++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            } else if (i < m) {
                arr[idx++] = nums1[i++];
            } else if (j < n) {
                arr[idx++] = nums2[j++];
            }
        }
        System.arraycopy(arr, 0, nums1, 0, total);
    }
}

C++ 代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int total = m + n, idx = 0;
        vector<int> arr(total);
        for (int i = 0, j = 0; i < m || j < n;) {
            if (i < m && j < n) {
                arr[idx++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            } else if (i < m) {
                arr[idx++] = nums1[i++];
            } else if (j < n) {
                arr[idx++] = nums2[j++];
            }
        }
        copy(arr.begin(), arr.end(), nums1.begin());
    }
};

Python 代码：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        total, idx = m + n, 0
        arr = [0] * total
        i, j = 0, 0
        while i < m or j < n:
            if i < m and j < n:
                if nums1[i] < nums2[j]:
                    arr[idx] = nums1[i]
                    i += 1
                else:
                    arr[idx] = nums2[j]
                    j += 1
                idx += 1
            elif i < m:
                arr[idx] = nums1[i]
                idx += 1
                i += 1
            elif j < n:
                arr[idx] = nums2[j]
                idx += 1
                j += 1

        for i in range(total):
            nums1[i] = arr[i]

TypeScript 代码：

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let total = m + n, idx = 0;
    const arr = new Array(total);
    for (let i = 0, j = 0; i < m || j < n;) {
        if (i < m && j < n) {
            arr[idx++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        } else if (i < m) {
            arr[idx++] = nums1[i++];
        } else if (j < n) {
            arr[idx++] = nums2[j++];
        }
    }
    for (let i = 0; i < total; i++) nums1[i] = arr[i];
};

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

双指针 - 原地合并

上述两类做法都不是最优：

要么使用到了“排序”操作，时间复杂度带 $\log$，不是最优
要么使用到了“额外辅助数组”空间，空间复杂度不为 $O(1)$，也不是最优

那么是否有“不排序”且“不消耗额外空间”的原地做法呢？

答案是有的。

使用两个指针 i 和 j 分别指向 nums1 和 nums2 的结尾位置，从后往前地原地构造出答案。

所谓的原地构造是指：直接将 $nums1[i]$ 和 $nums2[j]$ 之间的较大值，放到合并后该在 nums1 出现的位置。

这也是为什么我们要「从后往前」而不是「从前往后」的原因。

使用 idx 代表当构造到答案的下标值，起始有 idx = m + n - 1（答案是一个长度为 $m + n$ 的数组，因此下标是 $m + n - 1$），根据指针 i 和 j 所达位置，以及 $nums1[i]$ 和 $nums2[j]$ 大小关系，分情况讨论：

若 i 和 j 任一到达边界，说明其中一个数组已用完，用另一数组的剩余元素进行填充即可
若 i 和 j 均未到达边界，进一步比较 $nums1[i]$ 和 $nums2[j]$ 的大小关系：
- 若 $nums1[i] > nums2[j]$，说明在合并答案中 $nums1[i]$ 出现 $nums2[j]$ 后面，将 $nums1[i]$ 填入到 $nums1[idx]$ 中，让 idx 和 i 同时前移
- 否则，将 $nums2[j]$ 填入到 $nums1[idx]$ 中，让 idx 和 j 同时前移

直到 i 和 j 均到达边界，此时合并答案已全部填充到 nums1 中。

Java 代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, idx = m + n - 1;
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j >= 0) {
                nums1[idx--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
            } else if (i >= 0) {
                nums1[idx--] = nums1[i--];
            } else {
                nums1[idx--] = nums2[j--];
            }
        }
    }
}

C++ 代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, idx = m + n - 1;
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j >= 0) {
                nums1[idx--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
            } else if (i >= 0) {
                nums1[idx--] = nums1[i--];
            } else {
                nums1[idx--] = nums2[j--];
            }
        }
    }
};

Python 代码：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, idx = m - 1, n - 1, m + n - 1
        while i >= 0 or j >= 0:
            if i >= 0 and j >= 0:
                if nums1[i] > nums2[j]:
                    nums1[idx] = nums1[i]
                    i -= 1
                else:
                    nums1[idx] = nums2[j]
                    j -= 1
                idx -= 1
            elif i >= 0:
                nums1[idx] = nums1[i]
                idx, i = idx - 1, i - 1
            else:
                nums1[idx] = nums2[j]
                idx, j = idx - 1, j - 1

TypeScript 代码：

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m - 1, j = n - 1, idx = m + n - 1;
    while (i >= 0 || j >= 0) {
        if (i >= 0 && j >= 0) {
            nums1[idx--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
        } else if (i >= 0) {
            nums1[idx--] = nums1[i--];
        } else {
            nums1[idx--] = nums2[j--];
        }
    }
};

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.88 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

双指针排序

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 80. 删除有序数组中的重复项 II 上一篇

LC 781. 森林中的兔子下一篇