合并两个有序数组

分析

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

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

还能不能进一步优化呢？

仔细观察例子，不难看出 nums1 数组元素数量永远比 nums2 大，且当数组索引大于 $m$ 时其值为 0。 再回想下我们上一个解法中，创建一个新数组是为了避免值被覆盖。 那如果我们从后面开始逆序遍历，因为 $m$ 小于 nums1.size()，且 $n < m$， 所以就算覆盖了也没关系。¹ 我们仅需要再添加一个指针 tail 用于存储 m + n - 1 ，让其分别与 $m$、$n$ 比较即可。 由于这是从后面开始遍历，所以开始值与结束条件我们也需要变换。 此时，空间复杂度压缩到了 $O(1)$。

在这基础上，我们可以做一些小优化： 由于 $n < m$，所以我们实际上仅需要考虑 $p_2 \geq 0$ 的情况即可。 在这样的情况下，我们也无需在控制语句中判断 $j < 0$ 的情况。 这能让内存占用进一步减少，运行速度变得更快。

解答

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

    while (p2 >= 0) {
      if (p1 >= 0 && nums1[p1] > nums2[p2])
        nums1[tail--] = nums1[p1--];
      else
        nums1[tail--] = nums2[p2--];
    }
  }
};

脚注