HJ80. 整型数组合并
题目描述
给定两个升序排列的整数数组，将它们合并，去重后按升序输出。
输入格式
- 第 1 行：第一个数组的元素个数 n1
- 第 2 行：第一个数组的 n1 个数
- 第 3 行：第二个数组的元素个数 n2
- 第 4 行：第二个数组的 n2 个数
输出格式
合并去重排序后的数组。注意：元素之间不加空格，直接拼接输出。
示例
示例 1
输入：
3
1 2 5
4
-1 0 3 2
输出：
-101235
说明：
两个数组合并为 1 2 5 -1 0 3 2，去重排序后得到 -1 0 1 2 3 5，元素间不加空格拼接为 -101235。
示例 2
输入：
1
11
1
111
输出：
11111
说明：
合并去重排序后为 [11, 111]，拼接为 11111。
解题思路
第一步：理解问题本质
把两个数组合并，去掉重复元素，最终按升序输出。结果集合等于两个数组的并集。
第二步：暴力解法（逐个比较去重）
把 B 的元素逐个插入 A，插入时检查是否重复，保持有序。每次插入需 O(n) 移动，总复杂度偏高。
第三步：优化解法（集合 + 排序）
利用 Python 内置 set 天然去重，再排序：
merged = sorted(set(arr1) | set(arr2))
集合的并运算 O(n1+n2)，排序 O((n1+n2)·log(n1+n2))，简洁高效。
第四步：最优解法（归并去重）
输入数组本身已有序，可借归并思想在 O(n1+n2) 内合并去重：同时遍历两个数组，取较小者加入结果，跳过与结果末尾相同的元素。时间复杂度最优，但代码较繁琐，本题数据量不大，集合法足够。
完整代码实现
算法可视化 · 逐帧回放这道题的代码5 帧 · 录制输入
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
it = iter(data)
n1 = int(next(it))
arr1 = [int(next(it)) for _ in range(n1)]
n2 = int(next(it))
arr2 = [int(next(it)) for _ in range(n2)]
merged = sorted(set(arr1) | set(arr2)) # 合并 + 去重 + 排序
print(''.join(map(str, merged))) # 元素间不加空格
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，arr1 = [1, 2, 5]，arr2 = [-1, 0, 3, 2]。
set(arr1) = {1, 2, 5}set(arr2) = {-1, 0, 3, 2}- 并集
= {-1, 0, 1, 2, 3, 5} - 排序后
= [-1, 0, 1, 2, 3, 5]
输出 -101235（元素间不加空格），正确。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐个插入 | O(n1·n2) | O(n1+n2) | 插入需移动元素 |
| 集合+排序 | O(N·log N) | O(N) | N = n1+n2，简洁 |
| 归并去重 | O(N) | O(N) | 利用已有序，最优 |
N = n1 + n2 为元素总数
易错点总结
1. 忘记去重
题目要求去重，直接拼接两个数组再排序会输出重复元素，错误。
2. 集合未转回列表就取下标
set 是无序的，必须经过 sorted() 得到有序列表后再 join。
3. 读入数量不匹配
输入包含两个数组各自的长度 n1、n2，读取时必须按长度分别取数，不能混在一起。
4. 输出不加空格
题目要求元素之间不输出空格，要用 ''.join(map(str, merged)) 拼接，而不是 ' '.join(...)。这也是本题最容易失分的地方。
扩展思考
- 归并去重是经典双指针应用，适合处理超大数组（无法一次性排序的流式数据）。
- 集合运算
|、&、-分别对应并、交、差，可扩展解决数组集合运算类问题。