四路有序数组高效归并：基于最小堆的 O(n) 合并算法实现

这是一个**多路归并（k-way merge）**问题：给定 **4 个已排序的数组**（长度均为 `n`），要求将它们**合并成一个升序排列的数组**并输出。 --- ### ✅ 解题思路 由于每个序列都已有序，我们可以使用**最小堆（优先队列）**来高效地进行多路归并： - 将每个序列的第一个元素（及其所属序列索引、当前下标）放入最小堆； - 每次取出堆顶最小元素，加入结果； - 然后将该元素所在序列的下一个元素（如果存在）推入堆中； - 重复直到堆为空。 时间复杂度：**O(4n log 4) = O(n)**（因为堆大小最多为 4） 空间复杂度：**O(4) = O(1)**（额外空间仅用于堆） > 💡 注意：虽然有 4 个序列，但 `log 4` 是常数，所以整体是线性的。 --- ### ✅ Python 实现（使用 `heapq`） ```python import heapq n = int(input().strip()) # 读入四个序列 a = list(map(int, input().split())) b = list(map(int, input().split())) c = list(map(int, input().split())) d = list(map(int, input().split())) # 构建初始堆：(value, list_id, index) # list_id: 0->a, 1->b, 2->c, 3->d heap = [] if a: heapq.heappush(heap, (a[0], 0, 0)) if b: heapq.heappush(heap, (b[0], 1, 0)) if c: heapq.heappush(heap, (c[0], 2, 0)) if d: heapq.heappush(heap, (d[0], 3, 0)) # 所有序列 lists = [a, b, c, d] result = [] while heap: val, lst_id, idx = heapq.heappop(heap) result.append(val) # 推入该列表的下一个元素（如果存在） if idx + 1 < n: next_val = lists[lst_id][idx + 1] heapq.heappush(heap, (next_val, lst_id, idx + 1)) # 输出结果 print(" ".join(map(str, result))) ``` --- ### ✅ 运行样例验证 输入： ``` 5 2 3 6 7 9 1 4 5 8 10 1 2 3 5 6 1 1 1 1 1 ``` 过程简述（前几步）： - 初始堆：`(1,1,0)`, `(1,2,0)`, `(1,3,0)` → 最小是 `1`（来自 b/c/d 中任一，Python heapq 稳定性不保证顺序，但值相同即可） - 后续不断取最小，插入后续元素，最终得到： ``` 1 1 1 1 1 1 1 2 2 3 3 4 5 5 6 6 7 8 9 10 ``` ✅ 完全匹配样例输出。 --- ### 🧠 补充说明（进阶思考） - 若序列长度不等？→ 上述代码稍作修改（用 `len(lists[i])` 替代 `n` 判断边界）即可通用。 - 若序列数量 `k` 很大（比如 1000）？→ 仍适用，时间复杂度 `O(N log k)`，其中 `N` 是总元素个数。 - 是否可用 `sorted(a+b+c+d)`？→ 可以，但时间复杂度 `O(4n log(4n))`，不如堆解法优雅高效，尤其当 `n` 很大时。 --- ######[AI写代码神器 | 901点数解答 | 2026-03-18 17:46:32]