LC88. 合并两个有序数组

题目描述

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

题目解析

题目在说什么

这道题给你两个已经从小到大排好序的数组：nums1 和 nums2。 nums1 的长度是 m + n，但前面只有 m 个有效数字，后面 n 个位置是空的（用 0 占位）。 nums2 有 n 个有效数字。 你的任务是把 nums2 的所有数字合并到 nums1 里，让 nums1 最终变成一个完整的有序数组，而且不能新开一个数组，只能用 nums1 自己的空间。

举个例子： nums1 = [1, 2, 3, 0, 0, 0]，m = 3 nums2 = [2, 5, 6]，n = 3 合并后 nums1 应该变成 [1, 2, 2, 3, 5, 6]。

---

思路是怎么来的

想象你面前有两叠扑克牌，每叠都已经从小到大排好了。 你要把它们合并成一叠，并且仍然从小到大排好。 通常的做法是：从两叠牌的最上面（最小）开始，每次比较两张牌，把小的那张放到新牌叠里。 但是这里有个限制：我们只能把结果放到 nums1 里，不能另找地方。

如果从前面（最小的位置）开始放，会有一个麻烦：nums1 前面已经有数字了，你放一个新数字进去，可能会把原来的数字盖住。 比如 nums1 = [1, 2, 3, 0, 0, 0]，如果从最前面开始比较，把 nums2 的第一个数字 2 放到 nums1[0]，那原来的 1 就被覆盖了，后面就乱了。

所以我们可以反过来想：从后面（最大的位置）开始放。 因为 nums1 后面是空的，我们从后往前放数字，就不会覆盖还没处理的有效数字。 而且，两个数组都已经有序，所以最大的数字一定在某个数组的末尾。 我们每次比较两个数组的末尾数字，把大的那个放到 nums1 的最后面，然后往前移动，这样一步步就把所有数字都放好了。

这个过程就像：你手里有两叠牌，每叠都是从小到大排好的，但你不想从前面拿，而是从后面拿最大的牌，一张一张放到新牌叠的末尾。这样放完，新牌叠自然就是从小到大排好的。

---

代码逐步拆解

我们来看代码，一行一行解释它在干什么，以及为什么这么写。

int i = m - 1;

• i 指向 nums1 有效部分的最后一个元素。

比如 nums1 = [1, 2, 3, 0, 0, 0]，m = 3，那么 i = 2，指向数字 3。

int j = n - 1;

• j 指向 nums2 的最后一个元素。

比如 nums2 = [2, 5, 6]，n = 3，那么 j = 2，指向数字 6。

int cur = nums1.length - 1;

• cur 指向 nums1 的最后一个位置（也就是整个数组的末尾）。

这个位置是空的（或者说是 0），我们要从这里开始放最大的数字。

while( j >= 0 )

• 循环条件是 j >= 0，意思是只要 nums2 里还有数字没放完，就继续。

当 nums2 全部放完时，nums1 里剩下的数字本来就在正确位置，不需要再处理了。

if( i >= 0 && nums1[i] > nums2[j] )

• 比较两个数组当前指向的数字。

注意要先判断 i >= 0，因为 nums1 的有效数字可能先被取完（比如 i 变成 -1），这时就不能再比较 nums1[i] 了，否则会出错。 如果 nums1[i] 更大，就把这个数字放到 cur 位置。

nums1[cur] = nums1[i];
cur--;
i--;

• 把 nums1[i] 放到 nums1[cur]，然后 cur 和 i 都向前移动一位。