合并两个有序数组

分析

这题一眼就能看出要用双指针，不过如何灵活运用就是另外一回事了。

我首先想到的是创建一个新的数组，然后利用两层循环逐个比较。 这种暴力做法显然不是最优解，光时间复杂度就已经达到了 $O(m\times n)$。 此时问题自然而然地集中在如何合并成一个循环上。 该如何合并呢？ 经过提示不难想出我们可以利用已排列数组这个特性，通过比较 p1、p2 所指向的值， 从而有选择地插入。 这样下来，时间复杂度被压缩到 $O(m + n)$ ，空间复杂度为 $O(m + n)$。

还能不能进一步优化呢？

仔细观察题意，不难看出 nums1 的总长度为 m + n，其后半部分预留了足够空间用于合并结果。 再回想下我们上一个解法中，创建一个新数组是为了避免值被覆盖。 那如果我们从后面开始逆序遍历，就可以优先填写最终数组的尾部，因此即使覆盖 nums1 中原有元素，也不会影响尚未比较的内容。¹ 我们仅需要再添加一个指针 tail 用于存储 m + n - 1 ，让其分别与 $m$、$n$ 比较即可。 由于这是从后面开始遍历，所以开始值与结束条件我们也需要变换。 此时，空间复杂度压缩到了 $O(1)$。

在这基础上，我们可以做一些小优化： 由于当 p2 < 0 时，nums2 已经全部合并完成，所以我们实际上只需要继续判断 p2 >= 0 的情况即可。 在这样的情况下，我们也无需在控制语句中额外判断 p1 < 0 之外的冗余分支。 这能让内存占用进一步减少，运行速度变得更快。

解答

1
class Solution {
2
public:
3
  void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
4
    auto p1 = m - 1;
5
    auto p2 = n - 1;
6
    auto tail = m + n - 1;
7

8
    while (p2 >= 0) {
9
      if (p1 >= 0 && nums1[p1] > nums2[p2])
10
        nums1[tail--] = nums1[p1--];
11
      else
12
        nums1[tail--] = nums2[p2--];
13
    }
14
  }
15
};

脚注