求M个有序数组的并集
哪些公司问过
答案要点
- 小顶堆维护每个数组的当前元素,堆大小不超过 M
- 每次弹出堆顶,与结果末尾比较去重后追加
- 弹出后把同一数组的下一个元素入堆
- 时间 O(N log M),堆空间 O(M)
- M=2 时双指针 O(N),也可分治两两合并
易错点
- 只和堆顶前一个比较,同一数组内的重复没去掉
- 把所有元素都放进堆,复杂度变成 O(N log N)
- 弹出后忘记推进对应数组的下标
面试官常见追问
- 如果要求交集呢?
- 数据量大到内存放不下怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场