如何快速找到数组的中位数(快速选择)
哪些公司问过
答案要点
- 排序取中间 O(n log n);快速选择平均 O(n)
- 划分后只递归目标所在一侧,期望工作量 n + n/2 + … 为线性
- 最坏 O(n²),随机基准规避;BFPRT 保证最坏线性但常数大
- 偶数长度取两个中间值平均;C++ 可用 std::nth_element
- 数据流动态中位数用大顶堆加小顶堆,插入 O(log n),查询 O(1)
易错点
- 固定选第一个元素作基准,遇到有序数组退化成 O(n²)
- 划分后两侧都递归,变成了快排
- 偶数长度只取一个中间值,没有按题意处理
面试官常见追问
- 如果题目说的 select 是指 IO 多路复用的 select,它和 epoll 有什么区别?
- 数据量大到内存放不下怎么求中位数?
- 数据流中位数的双堆法怎么维护?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。