合并两个无序数组并升序排序
哪些公司问过
答案要点
- 基本解法:拼接后整体排序,时间 O((m+n)log(m+n)),空间 O(m+n)
- 进阶解法:两数组分别排序后双指针归并,归并阶段 O(m+n),一边耗尽后直接拷贝另一边剩余元素
- 值域有限的整数可用计数排序,时间 O(m+n+k),k 为值域大小
- 先和面试官确认是否去重、是否允许额外空间、数据规模和值域,再选方案
- 原地合并(第一个数组尾部有足够空间)时从后往前填充,避免覆盖未处理元素
易错点
- 归并时一侧走完后忘了把另一侧剩余元素追加进结果
- 没有确认是否需要去重就直接写代码
- 原地合并时从前往后写,覆盖了尚未比较的元素
- 误以为先各自排序再归并在复杂度上一定优于直接整体排序
面试官常见追问
- 如果结果要求去重怎么办?
- 如果是 k 个有序数组合并呢?
- 两个数组都非常大、内存放不下怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场