88. 合并两个有序数组

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

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

/**
 * 合并数组后，排序
 * 时间复杂度：O((m+n)log(m+n))
 * 空间复杂度：O(log(m+n))
 */
var merge = function (nums1, m, nums2, n) {
  nums1.splice(m, nums1.length - m, ...nums2)
  return nums1.sort((a, b) => a - b)
};

/**
 * 双指针
 * 时间复杂度：O(m+n)
 * 空间复杂度：O(m+n)
 */
var merge = function (nums1, m, nums2, n) {
  const res = new Array(m + n).fill(null)
  let l1 = 0
  let l2 = 0
  let cur
  while (l1 < m || l2 > n) {
    if (l1 === m) {
      cur = nums2[l2++]
    } else if (l2 === n) {
      cur = nums1[l1++]
    } else if (nums1[l1] < nums2[l2]) {
      cur = nums1[l1++]
    } else {
      cur = nums2[l2++]
    }
    res[l1 + l2 - 1] = cur
  }
  for (let i = 0; i < res.length; i++) {
    nums1[i] = res[i]
  }
};

/**
 * 逆向双指针
 * 时间复杂度：O(m+n)
 * 空间复杂度：O(1)
 */
var merge = function (nums1, m, nums2, n) {
  let p1 = m - 1
  let p2 = n - 1
  let tail = m + n - 1
  let cur
  while (p1 >= 0 || p2 >= 0) {
    if (p1 < 0) {
      cur = nums2[p2--]
    } else if (p2 < 0) {
      cur = nums1[p1--]
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--]
    } else {
      cur = nums2[p2--]
    }
    nums1[tail--] = cur
  }
}