88. 合并两个有序数组
题目描述
输入两个非递减的整数数组 nums1、nums2，以及整数 m、n。nums1 的前 m 个元素是有效数据，后 n 个位置是占位用的 0，应当忽略；nums2 恰好有 n 个元素。
把 nums2 并入 nums1，使 nums1 的全部 m + n 个元素仍然非递减。
结果直接写在 nums1 里，函数不返回值。示例输出展示的是合并后的 nums1。
示例 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] 合并。
示例 2
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1]
解释：nums2 为空，nums1 不变。
示例 3
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1]
解释：m = 0，nums1 里的 0 只是占位，合并后就是 [1]。
数据范围
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-10^9 <= nums1[i], nums2[j] <= 10^9
进阶：能否在 O(m + n) 时间内完成？
解题思路
从后往前填。i 指向 nums1 有效部分的末尾，j 指向 nums2 末尾，k 指向 nums1 最后一个位置。每次把 nums1[i] 和 nums2[j] 中较大的放到 nums1[k]，对应指针和 k 各左移一位。nums2 放完就结束，nums1 剩下的元素已经在正确位置。
为什么正确
nums1[k+1:] 是全体元素中最大的 m+n−k−1 个，已排好序；并且 k = i + j + 1，所以写入 nums1[k] 不会覆盖还没读的 nums1[i]。
复杂度分析
时间 O(m + n)，空间 O(1)。
易错点
从前往后合并会覆盖 nums1 中还没读的元素。循环条件写 j >= 0 即可；若写成 i >= 0 and j >= 0，要记得把 nums2 剩余的元素补进去。m = 0 时 i 一开始就是 -1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
}
}class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
}
};func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
for j >= 0 {
if i >= 0 && nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
}var merge = function(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
};function merge(nums1: number[], m: number, nums2: number[], n: number): void {
let i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
}