描述
给你两个有序整数数组 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
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
1
2
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
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
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
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
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。