88.合并两个有序数组

题目

LeetCode 简单

INFO

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

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

示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1 ,2 ,2, 3,5,6] ，其中加粗标注的为 nums1 中的元素。

题解

方法：逆向双指针

逆向双指针 O(m+n) O(1)

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  if (n === 0) return

  let len = m + n - 1
  let i1 = m - 1
  let i2 = n - 1
  while (i2 > -1) {
    let n1 = nums1[i1]
    let n2 = nums2[i2]

    if (n1 > n2) {
      nums1[len] = n1
      i1--
    } else {
      nums1[len] = n2
      i2--
    }

    len--
  }
}

const nums1 = [1, 2, 3, 0, 0, 0],
  m = 3,
  nums2 = [2, 5, 6],
  n = 3

// const nums1 = [-1, -1, 0, 0, 0, 0],
// m = 4,
// nums2 = [-1, 0],
// n = 2

// const nums1 = [1],
//   m = 1,
//   nums2 = [],
//   n = 0

// const nums1 = [0],
//   m = 0,
//   nums2 = [1],
//   n = 1

merge(nums1, m, nums2, n)
console.log('🌰', nums1)

方法：双指针

双指针 O(m+n) O(m+n)

function merge2(nums1: number[], m: number, nums2: number[], n: number): void {
  let i1 = 0
  let i2 = 0

  const sortedArr = new Array(m + n).fill(0)
  let si = 0

  while (si < m + n) {
    const v1 = nums1[i1]
    const v2 = nums2[i2]

    if (i1 === m) {
      sortedArr[si] = v2
      i2++
    } else if (i2 === n) {
      sortedArr[si] = v1
      i1++
    } else if (v1 < v2) {
      sortedArr[si] = v1
      i1++
    } else {
      sortedArr[si] = v2
      i2++
    }

    si++
  }

  for (let i = 0; i < m + n; i++) {
    nums1[i] = sortedArr[i]
  }
}

const nums3 = [1, 2, 3, 0, 0, 0],
  m2 = 3,
  nums4 = [2, 5, 6],
  n2 = 3

merge2(nums3, m2, nums4, n2)
console.log('🌰', nums3)

方法：合并后排序

排序序列长度为 m+n，套用快速排序，时间复杂度：O((m+n)log⁡(m+n)) 空间复杂度：O(log(m+n))

function merge3(nums1: number[], m: number, nums2: number[], n: number): void {
  nums1.splice(m, nums1.length - m, ...nums2)
  nums1.sort((a, b) => a - b)
}

const nums5 = [1, 2, 3, 0, 0, 0],
  m3 = 3,
  nums6 = [2, 5, 6],
  n3 = 3

merge3(nums5, m3, nums6, n3)
console.log('🌰', nums3)