按权重比例随机选取元素
哪些公司问过
虎牙直播1松鼠AI1
答案要点
- 计算权重前缀和,总权重为最后一项
- 生成 [0, 总权重) 的随机数 r,选第一个前缀和大于 r 的元素
- 选中概率等于该元素权重除以总权重
- 前缀和递增可二分查找,预处理 O(n),单次查询 O(log n);高频查询可用别名法 O(1)
- 边界:权重为 0、总权重为 0、前缀和溢出、随机数区间开闭
易错点
- 随机数区间开闭和比较符号搞错,导致边界元素概率偏差
- 每次查询都重新计算前缀和,复杂度退化
- 忽略权重为 0 或总权重为 0 的情况
面试官常见追问
- 权重会动态变化怎么办?
- 用 rand() % total 有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。