随机取数算法的实现(C++)
哪些公司问过
答案要点
- 区间等概率用mt19937配合uniform_int_distribution
- rand()取模有偏差且范围有限
- 不重复取k个用Fisher-Yates洗牌,部分洗牌O(k)
- 数据流用蓄水池抽样,每个元素被选中概率为k/n
- 种子只初始化一次,不要每次调用重新播种
易错点
- 用rand()%n导致分布不均
- 每次取数都重新设置种子,结果重复
- 洗牌时与整个数组的随机位置交换,导致非均匀排列
面试官常见追问
- 蓄水池抽样为什么是等概率的?
- 按权重随机取数怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。