合并两个有序数组
P5500. 合并两个有序数组
场次:2026年10月20日-AI方向 · 来源:CodeFun2000 P5500
题目描述
给你两个按非递减顺序排列的整数数组 和 ,另有两个整数 和 ,分别表示 和 中的元素数目。
请你合并 到 中,使合并后的数组同样按非递减顺序排列。
最终排序后的数组应存储在 中。 的初始长度为 ,其中前 个元素表示应合并的元素,后 个元素为 ,应忽略。 的长度为 。
输入格式
第一行输入两个整数 (,),表示两个数组的有效元素数目。
第二行输入 个整数,表示数组 (前 个为有效元素,后 个为 )。
第三行输入 个整数,表示数组 。数组元素范围 。
输出格式
输出合并后的数组,数字之间以空格分隔。
示例
示例 1
输入:
3 3
1 2 3 0 0 0
2 5 6输出:
1 2 2 3 5 6说明:
将 合并到 中,结果为 。
示例 2
输入:
1 0
1输出:
1说明:
,第三行没有数字, 是空数组; 的有效部分就是合并结果。
解题思路
原地合并的难点只有一个:往哪个方向写
数组已经有序,两个指针各走一段、每次取较小的那个放进去,这是归并排序里最熟的写法。但这里是原地合并,写入的位置和读取的位置共用一个数组,方向选错就会把还没读的数据盖掉。
从前往后写,必须先复制一份有效部分,否则写进去的元素正好压住还没读的那个:
def merge_with_copy(nums1, m, nums2, n):
"""先抄出 nums1 的有效部分,再从前向后归并:正确,但要 O(m) 额外空间。"""
left = nums1[:m]
i = j = k = 0
while i < m and j < n:
if left[i] <= nums2[j]:
nums1[k] = left[i]
i += 1
else:
nums1[k] = nums2[j]
j += 1
k += 1
# 两段里剩下的那一段整体搬到尾部
while i < m:
nums1[k] = left[i]
i += 1
k += 1
while j < n:
nums1[k] = nums2[j]
j += 1
k += 1
return nums1left 这一行不是可省的:写入位置 k 永远不大于读指针 i,不复制的话,写进去的那一笔就落在还没读的元素上。用示例 1 走一遍,第 3 次写入是 nums1[2] = 2,而位置 2 原本存着 3——复制版本里 3 早已躺在 left 中,不复制就被这一笔盖掉。省不省这份复制,就是 空间与 空间的分界。
空位在尾部,就从尾部往前填
题面把 个空位放在 nums1 的末尾,这不是偶然——它正好是「从后往前写」的缓冲区。两段数据的最大值分别在各自末尾,把较大的那个放进 nums1 的最后一个空位,这个位置永远不会是「还没读过的有效元素」:
def merge(nums1, m, nums2, n):
i = m - 1 # nums1 有效部分的末尾
j = n - 1 # nums2 的末尾
k = m + n - 1 # 待填写的末尾空位
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
return nums1每轮写入后 k 减一,而 i 只在 nums1[i] 被搬走时才减一,两者同步倒退,k >= i 始终成立。所以写 nums1[k] 时,这个位置要么在 i 的右边(还没填的空位),要么就是 i 自己(那个元素刚好被搬走),不会碰到任何还没比较的元素。
循环结束时谁还有剩余
while i >= 0 and j >= 0 退出的条件是某一侧先耗尽,两种情况要分开看:
j < 0:nums2搬完了。nums1前 个元素本来就在正确位置(它们是剩下元素里最小的那批,原地不动即可),循环可以直接结束。i < 0:nums1的有效部分搬完了,nums2还剩 个元素。这些元素全都小于已放置的所有元素,必须继续搬到nums1的前部,否则它们根本不在结果里。
补上缺的那一段(接在上面的主循环之后、return 之前):
# nums1 剩下的元素本来就在前缀里,不用搬;nums2 剩下的必须继续搬
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
return nums1这段补丁是本题最容易漏的一行:漏了它,示例 1 依然能过(nums2 的元素都比较大,先搬完的是 nums2),但 nums1 = [4,5,6]、nums2 = [1,2,3] 这种「nums2 全小」的输入就只剩前一段。
完整代码实现
import sys
def merge(nums1, m, nums2, n):
i = m - 1 # nums1 有效部分的末尾
j = n - 1 # nums2 的末尾
k = m + n - 1 # 待填写的末尾空位
while i >= 0 and j >= 0:
# 取两段末尾较大的那个,放进当前最靠后的空位
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
# nums1 剩下的元素本来就在前缀里,不用搬;nums2 剩下的必须继续搬
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
return nums1
def solve():
data = sys.stdin.read().split()
if not data:
return
pos = 0
m = int(data[pos])
n = int(data[pos + 1])
pos += 2
nums1 = list(map(int, data[pos:pos + m + n]))
pos += m + n
nums2 = list(map(int, data[pos:pos + n]))
merge(nums1, m, nums2, n)
print(' '.join(map(str, nums1)))
if __name__ == "__main__":
solve()示例推演
示例 1:nums1 = [1,2,3,0,0,0]、nums2 = [2,5,6]
初始 i = 2(值 3)、j = 2(值 6)、k = 5。
| 轮次 | nums1[i] | nums2[j] | 写入位置 | nums1 状态 | 之后 |
|---|---|---|---|---|---|
| 1 | 3 | 6 | nums1[5] = 6 | [1,2,3,0,0,6] | j=1, k=4 |
| 2 | 3 | 5 | nums1[4] = 5 | [1,2,3,0,5,6] | j=0, k=3 |
| 3 | 3 | 2 | 3 > 2,nums1[3] = 3 | [1,2,3,3,5,6] | i=1, k=2 |
| 4 | 2 | 2 | 相等走 else,nums1[2] = 2 | [1,2,2,3,5,6] | j=-1, k=1 |
第 4 轮后 j = -1,循环结束。i = 1,nums1 的前两个元素 [1,2] 本来就在正确位置,补 nums2 的循环不执行。输出 1 2 2 3 5 6。
第 4 轮的平局走 else 分支:nums2 的元素先落位,nums1 的那个 2 留在 i 处——两数相等时谁先放都不破坏有序性,而循环随即因为 j = -1 结束,它本来就站在正确的位置上。
示例 2:m = 1、n = 0
nums1 = [1](长度 ,全是有效元素,没有占位 0),nums2 = []。初始 i = 0、j = -1、k = 0。主循环的第二个条件 j >= 0 不成立,一轮都不进;补 nums2 的循环同样因为 j = -1 不执行。nums1 原样输出 1。
这个用例是「nums2 为空」的边界:第三行一个数字都没有,solve 读出的 nums2 是空列表,merge 必须能直接接受它。
另一条边界:m = 0
m = 0 时 nums1 的 m+n 个位置全是占位 0,答案完全来自 nums2。取 m = 0、n = 1,输入是 nums1 = [0]、nums2 = [1]:初始 i = -1、j = 0、k = 0,主循环因为 i < 0 一轮都不进,补 nums2 的循环把 1 写进 nums1[0],输出 1。这一侧才是 while j >= 0 那段补丁的唯一执行路径。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
复制 nums1 有效部分后从前向后归并 | 逻辑最直白,但要额外数组,不满足原地要求 | ||
| 从后向前双指针原地归并(最优) | 每个元素恰好搬一次,空位在尾部所以无需缓冲 |
主循环最多执行 次,每次写入一个元素,没有嵌套扫描。空间上只用了 i、j、k 三个下标;输入的解析另算,那是读数据的开销。
易错点总结
1. 漏掉补 nums2 的尾部循环
主循环写成 while i >= 0 and j >= 0 之后直接 return nums1,nums2 剩下的元素就丢了。输入 nums1 = [4,5,6,0,0,0]、nums2 = [1,2,3] 时,三轮都走 nums1[i] > nums2[j] 的分支,i 先到底,j 还剩 2;输出变成 4 5 6 4 5 6。示例 1 那种 nums2 偏大的用例完全测不出这个漏洞。
2. 从前往后写却不复制
把 merge_with_copy 里的 left = nums1[:m] 删掉、left[i] 全改成 nums1[i],就得到「原地从前向后写」的版本。k 永远不大于 i,第 3 次写入 nums1[2] = 2 会把原来的 3 盖掉,之后这个 3 再也不出现。输入 nums1 = [1,2,3,0,0,0]、nums2 = [2,5,6] 时输出 1 2 2 2 5 6——长度对、位置对,可原数组里的 3 已经没了,结果里多出一个 2。
3. 把占位的 0 当成有效数据
i 的初值取成 m + n - 1(而不是 m - 1),指针一开始就落在尾部那 个 0 上。0 > 6 不成立,于是整段 nums2 被当成「比 nums1 小」一直往右塞,示例 1 会输出 6 6 6 2 5 6:nums1 里原有的 1、2、3 被覆盖,k 还会走到负下标。m 与 的差别是这题唯一的下标约定,写错时编译、运行都不报错。
扩展思考
- 换成链表:两个有序链表合并只能从头部开始接,没法「从后往前填」,做法是用哑节点加尾指针,把较小的节点接上去,空间还是 。数组能倒着填,靠的正是「尾部有空位」这个存储布局,不是算法本身的对称性。
nums1没有尾部空位时:若两个数组都只占满自己长度、要求输出到第三个数组,从后往前就退化成「从后往前写新数组」——仍然是一次遍历,但必须有 的输出缓冲,空间换不回来。