Merge Sorted Array
你会得到两个整数数组 nums1 和 nums2。它们都已按非递减顺序排序。返回一个包含两个数组中所有值的数组，并且也按非递减顺序排列。两个数组中都出现的值，在结果中出现的次数等于它在两个数组中出现次数的总和。
函数
- nums1integer-array
- 第一个排序后的数组
- nums2integer-array
- 第二个已排序数组
- 返回值integer-array
- 将两个数组的所有值合并到一个排序后的数组中，长度为 nums1.length + nums2.length
约束条件
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1和nums2都已按非递减顺序排序。
示例
- 输入
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- 输出
- [1, 2, 3, 4, 9, 10]
- 解释
- 比较两个数组开头的值，保留较小的那个：1，然后是
nums2中的 2 和 3，接着是nums1中的 4 和 9，最后是 10。结果包含全部 6 个值。
- 输入
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- 输出
- [-5, 0, 0, 0, 6, 8]
- 解释
- 数字 0 在
nums1中出现两次，在nums2中出现一次，所以结果中有 3 个 0。-5 小于nums2中的所有数，并排在最前面。
- 输入
- nums1 = [7]nums2 = [3]
- 输出
- [3, 7]
- 解释
- 每个数组都包含一个值。3 小于 7，所以它排在前面。
进阶
你能否在 O(N log k) 时间内合并 k 个已排序数组，这些数组总共包含 N 个值？
提示
逐个打开提示，每个都会多透露一点。
两个数组都已经排好序了。整个结果中最小的值可能在哪里？
剩下的最小值总是在
nums1或nums2的开头。每个数组都用一个索引标记其开头的位置。比较两个数组的首项，追加较小的一项，并将对应的索引向前移动。当一个数组用完时，另一个数组剩下的部分已经排好序了，直接追加即可。
题解
两个数组都已排序，因此剩下的最小值始终位于其中一个数组的开头。为每个数组保留一个索引，每一步都取较小的开头值，只需遍历一次就能构建结果。这就是归并排序中的合并步骤。
拼接并排序
思路
将两个数组合并，并对结果排序。结果会按顺序保留每个值出现的次数。nums1 中有 m 个值，nums2 中有 n 个值时，排序的时间复杂度为 O((m + n) log(m + n))。对于这些限制来说，这已经足够快了，但这种方法没有利用给定数据的有序性。
算法
- 创建一个数组，先放入
nums1的值，再放入nums2的值。 - 按数值从小到大的顺序对它进行排序。
- 返回它。
def merge(nums1, nums2):
return sorted(nums1 + nums2)两个指针，每个数组一个
思路
索引 i 和 j 标记每个数组中第一个尚未使用的值。追加 nums1[i] 和 nums2[j] 中较小的值，并移动对应的索引。一个数组用完后，另一个数组剩下的部分已经有序，直接放到末尾即可。
每一步都会写入一个值，因此循环会运行 m + n 次：时间复杂度为 O(m + n)，结果是唯一的额外内存。
算法
- 将
i和j设为 0，并创建一个空结果。 - 当两个数组都还有值时，比较
nums1[i]和nums2[j]。 - 追加较小的值，并将它的索引向前移动。相等时，取
nums1[i]。 - 当一个数组用完时，将另一个数组剩下的值追加进来。
- 返回结果。
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
易错点和边界情况
- 一个数组用完后就停止，而忘记了另一个数组中剩下的元素。例如，使用
[1, 2, 3]和[4, 5, 6]时，循环会在处理完 1、2 和 3 后结束，而 4、5、6 仍需要复制。 - 在
i已到达末尾后读取nums1[i]。比较之前要检查两个索引。 - 丢掉重复项。
[0, 0]和[0]合并后得到[0, 0, 0]，而不是[0]。 - 在 JavaScript 和 TypeScript 中，不带比较器的
sort()会把数字当作文本排序，所以[-5, 10, 9]会保持为[-5, 10, 9]。传入(a, b) => a - b。
常见问题3
合并两个已排序数组的时间复杂度是多少？
使用双指针时，时间复杂度为 O(m + n)，其中 m 和 n 是两个数组的长度：每一步都会放入一个值。拼接后排序的时间复杂度为 O((m + n) log(m + n))。
如何原地合并两个已排序的数组？
如果第一个数组末尾有足够的空间容纳两者，就从后往前填充。比较两个数组中剩余的最大值，将较大的值写入最后一个空位，然后向左移动。从后往前写入，不会覆盖第一个数组中尚未放置的值。
合并两个已排序数组和归并排序的合并步骤是一样的吗？
是的。归并排序会将数组分成两半，分别排序，然后用这个双指针循环将两个已排序的部分合并。值相等时取左边的值，可以保留相等值原来的顺序，这正是归并排序稳定的原因。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def merge(nums1, nums2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
预期输出
[1, 2, 3, 4, 9, 10]