1、88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

方法一： 直接合并后排序

var merge = function (nums1, m, nums2, n) {
  // 替换为零的对象
  nums1.splice(m, nums1.length - m, ...nums2);
  // 从小到大递增排序
  nums1.sort((a, b) => a - b);
};

复杂度分析

• 时间复杂度：O((m+n)log⁡(m+n))。 排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log⁡(m+n))。

• 空间复杂度：O(log⁡(m+n))。 排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log⁡(m+n))。

方法二：双指针

var merge = function (nums1, m, nums2, n) {
  let p1 = 0,
    p2 = 0;
  const sorted = new Array(m + n).fill(0);
  var cur;
  while (p1 < m || p2 < n) {
    if (p1 === m) {
      // 当nums1已经添加完到sorted
      cur = nums2[p2++];
    } else if (p2 === n) {
      // 当nums2已经添加完到sorted
      cur = nums1[p1++];
    } else if (nums1[p1] < nums2[p2]) {
      cur = nums1[p1++];
    } else {
      cur = nums2[p2++];
    }
    sorted[p1 + p2 - 1] = cur;
  }
  for (let i = 0; i != m + n; ++i) {
    nums1[i] = sorted[i];
  }
};

复杂度分析

• 时间复杂度：O(m+n)。 指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

• 空间复杂度：O(m+n)。 需要建立长度为 m+n 的中间数组$\mathit{\text{ sorted }}$。

方法三：逆向双指针

var merge = function (nums1, m, nums2, n) {
  let p1 = m - 1,
    p2 = n - 1;
  let tail = m + n - 1;
  var cur;
  while (p1 >= 0 || p2 >= 0) {
    if (p1 === -1) {
      // 当
      cur = nums2[p2--];
    } else if (p2 === -1) {
      cur = nums1[p1--];
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--];
    } else {
      cur = nums2[p2--];
    }
    nums1[tail--] = cur;
  }
};

复杂度分析

• 时间复杂度：O(m+n)。 指针移动单调递减，最多移动m+n次，因此时间复杂度为 O(m+n)。

• 空间复杂度：O(1)。 直接对数组 ${\mathit{\text{nums}}}_1$原地修改，不需要额外空间。