乱序数据中求90分位值(P90)
哪些公司问过
答案要点
- 约定分位定义,如取第 ceil(0.9n) 小的元素
- 排序 O(n log n);快速选择平均 O(n),可用 nth_element
- 小顶堆保存最大的约 10% 元素,堆顶即 P90,O(n log(n/10))
- 值域有限时分桶计数,累计到 90% 即为答案,适合海量或流式
- 允许近似时可用 t-digest 等分位数草图
易错点
- 直接取乱序数组第 90% 位置的值
- 把多台机器的 P90 取平均作为整体 P90
- 分位位置的取整规则不明确,边界结果不一致
面试官常见追问
- 快速选择最坏情况是什么?
- 多台机器上的 P90 能直接取平均吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。