九旬的博客

描述

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

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 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]

1
2

示例 2：

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

1
2

提示：

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

1
2
3
4
5

题目链接：合并两个有序数组open in new window

解法

合并后排序

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

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

1
2
3
4

复杂度分析

时间复杂度：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;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

复杂度分析

时间复杂度：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--;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

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

总结

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

# 描述

# 解法

# 合并后排序

# 双指针

# 总结

描述

解法

合并后排序

双指针

总结