# 描述

给你两个有序整数数组  nums1nums2,请你将 nums2 合并到  nums1  中,使 nums1 成为一个有序数组。

初始化  nums1nums2 的元素数量分别为  mn 。你可以假设  nums1 的空间大小等于  m + n,这样它就有足够的空间保存来自 nums2 的元素。

示例 1:

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

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]

提示:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109

题目链接:合并两个有序数组 (opens new window)

# 解法

# 合并后排序

最简单的方式,先合并在排序。

let merge = function(nums1, m, nums2, n) {
  nums1.splice(m, nums1.length - m, ...nums2);
  nums1.sort((a, b) => a - b);
};

复杂度分析

  • 时间复杂度:O(n+m+(log(n+m)))
  • 空间复杂度:O(1)

# 双指针

分别遍历 nums1 和 nums2 每个元素,比对其大小,进行排序操作。

从前到后

拷贝一份新的数组,然后将 nums2 和 copyNums1 从前往后进行对比,依次插入 nums1 中,缺点是需要占用额外的空间(copyNums1)

let merge = function(nums1, m, nums2, n) {
  let copyNums1 = [...nums1]; // 创建一个和nums一样的数组
  let len1 = 0, // nums1 的长度
    len2 = 0, // nums2 的长度
    cur = null; // 待插入的元素
  while (len1 < m || len2 < n) {
    if (len1 === m) {
      // nums1 到头了 设置nums2
      cur = nums2[len2];
      len2++;
    } else if (len2 === n) {
      // nums2 到头了 设置nums1
      cur = copyNums1[len1];
      len1++;
    } else if (copyNums1[len1] < nums2[len2]) {
      // 比对大小 copyNums1的小 插入到nums1中
      cur = copyNums1[len1];
      len1++;
    } else {
      // 不符合以上三种情况的,直接插入nums2
      cur = nums2[len2];
      len2++;
    }
    console.log(len1, len2, cur);
    nums1[len1 + len2 - 1] = cur;
  }
};

复杂度分析

  • 时间复杂度:O(n+m)
  • 空间复杂度:O(m):新建的 copynums1 大小为 m

从后到前

不用创建新的空间,创建指针后直接在nums1上进行操作。

let merge = function(nums1, m, nums2, n) {
  let len1 = m - 1,
    len2 = n - 1,
    len3 = n + m - 1,
    cur = null;
  while (len1 >= 0 && len2 >= 0) {
    if (len1 == -1) {
      cur = nums2[len2];
      len2--;
    } else if (len2 === -1) {
      cur = nums1[len1];
      len1--;
    } else if (nums1[len1] > nums1[len2]) {
      cur = nums1[len1];
      len1--;
    } else {
      cur = nums2[len2];
      len2--;
    }
    nums1[len3] = cur;
    len3--;
  }
};

复杂度分析

  • 时间复杂度:O(n+m)
  • 空间复杂度:O(1)

# 总结

双指针的思维刚接触,有点难理解,需要花点时间慢慢梳理。参考解题方法,然后自己 debug。

上次更新: 4/23/2021, 2:14:10 PM