题目描述
这是 LeetCode 上的 88. 合并两个有序数组 。
Tag : 「双指针」、「排序」
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 复制代码
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 复制代码
提示：
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -10^9109 <= nums1[i], nums2[i] <= 10^9109
双指针（额外空间）
一个简单的做法是，创建一个和 nums1nums1 等长的数组 arrarr，使用双指针将
num1num1 和 nums2nums2 的数据迁移到 arrarr。
最后再将 arrarr 复制到 nums1nums1 中。
代码：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int total = m + n; int[] arr = new int[total]; int idx = 0; 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); } } 复制代码
- 时间复杂度：O(m + n)O(m+n)
- 空间复杂度：O(m + n)O(m+n)
先合并再排序
我们还可以将 nums2nums2 的内容先迁移到 nums1nums1 去，再对 nums1nums1 进行排序。
代码：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { System.arraycopy(nums2, 0, nums1, m, n); Arrays.sort(nums1); } } 复制代码
- 时间复杂度：O((m + n)log{(m + n)})O((m+n)log(m+n))
- 空间复杂度：O(1)O(1)
PS. Java 中的 sort 排序是一个综合排序。包含插入/双轴快排/归并/timsort，这里假定 Arrays.sort 使用的是「双轴快排」，并忽略递归带来的空间开销。
原地合并（从前往后）
也可以直接在 nums1nums1 进行合并操作，但是需要确保每次循环开始，nums2nums2 的指针指向的必然是最小的元素。
因此，我们需要对 nums2nums2 执行局部排序。
代码：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = 0, j = 0; while (j < n) { if (i >= m) { nums1[i] = nums2[j++]; } else { int a = nums1[i], b = nums2[j]; if (a > b) swap(nums1, i, nums2, j); sort(nums2, j, n - 1); } i++; } } void sort(int[] nums, int l, int r) { if (l >= r) return; int x = nums[l], i = l - 1, j = r + 1; while (i < j) { do i++; while (nums[i] < x); do j--; while (nums[j] > x); if (i < j) swap(nums, i, nums, j); } sort(nums, l, j); sort(nums, j + 1, r); } void swap(int[] nums1, int i, int[] nums2, int j) { int tmp = nums1[i]; nums1[i] = nums2[j]; nums2[j] = tmp; } } 复制代码
- 时间复杂度：O(n + m^2 log{m})O(n+m2logm)
- 空间复杂度：忽略递归开销，复杂度为 O(1)O(1)
原地合并（从后往前）
思路和「方法一」是类似的，将遍历方向由「从前往后」调整为「从后往前」即可做到 O(1)O(1) 空间复杂度。
代码：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1; int 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(m+n)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.88 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
