按权重(频率)随机采样索引
答案要点
- 前缀和把 [0, total) 划分为长度等于各频率的区间
- 生成 [0,1) 均匀随机数乘以 total,二分找第一个大于它的前缀和
- 预处理 O(n),每次采样 O(log n)
- 整数权重可用随机整数避免浮点误差,权重为 0 的下标不会被选中
- 浮点累计误差需兜底返回最后一个下标
易错点
- 二分边界写错,找成第一个大于等于浮点 r 的位置,导致权重为 0 的下标可能被选中
- 每次采样都重新计算前缀和,退化成 O(n)
- 忽略浮点误差,随机数落在最后一个前缀和之外时越界
面试官常见追问
- 采样次数非常多时能更快吗?
- 权重会动态修改怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。