K 个有序数组合并后的中位数
哪些公司问过
答案要点
- 中位数转第 k 小:奇数取第 (N+1)/2 小,偶数取第 N/2 与 N/2+1 小的平均
- 值域二分:对候选值 mid 统计各数组中不大于它的元素数
- 每个数组内用 upper_bound 计数,单轮 O(K log L)
- 总复杂度 O(K log L · log R),N 很大时优于堆归并的 O(N log K)
- 边界:空数组、mid 溢出、偶数个元素平均值用浮点
易错点
- 二分条件写错:应统计不大于 mid 的元素,并在总数 ≥ k 时收缩上界
- 偶数个元素时只取一个中间数
- 把复杂度说成 O(K log R),漏掉数组内二分的 log L
面试官常见追问
- K=2 时有什么更优的做法?
- 用堆怎么求第 k 小?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。