归并两个有序数组的时间与空间复杂度
哪些公司问过
答案要点
- 时间复杂度 O(m+n),每个元素只访问一次
- 双指针比较,较小元素先放入结果,一方耗尽后直接拼接另一方剩余部分
- 另开结果数组时空间 O(m+n)
- 若一个数组尾部有足够空间,从后往前填充,额外空间 O(1)
- 相等时取前一个数组的元素可保持稳定性
易错点
- 从前往后原地合并,覆盖了未处理的元素
- 忘记处理一个数组耗尽后另一个数组的剩余部分
- 把 k 路归并说成 O(Nk) 而不知道用堆优化
面试官常见追问
- 怎么归并 k 个有序数组?
- 怎么减少额外的内存占用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场