两个有序数组的中位数
哪些公司问过
答案要点
- 暴力:归并后取中位数,O(m+n);要求 O(log(m+n)) 必须用二分
- 转化为求两个有序数组合并后的第 k 小元素,k 为中间位置
- 划分法:对较短数组二分,使左半元素个数为 (m+n+1)/2,且左半最大值不大于右半最小值
- 奇数取左半最大值,偶数取左半最大值与右半最小值的平均
- 边界:某数组为空、划分点在端点,用正负无穷哨兵;复杂度 O(log(min(m,n)))
易错点
- 直接归并,不满足对数复杂度
- 对较长的数组做二分,下标越界
- 奇偶总长度处理混淆
- 没有处理空数组和端点划分
面试官常见追问
- 为什么只对较短的数组做二分?
- 用对顶堆怎么实时维护中位数?
- 求两个有序数组的第 k 大元素怎么做?
- 边界条件怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。