洗牌算法(Fisher-Yates)与随机选取
哪些公司问过
答案要点
- Fisher-Yates:从后向前,对下标 i 在 [0, i] 随机选 j 并交换,O(n),原地
- 每种排列出现的概率相等,均为 1/n!
- 错误写法:每次在 [0, n-1] 随机选下标交换,结果有偏
- 扫雷选 k 个地雷:位置编号成一维数组,只做前 k 步洗牌,取前 k 个,O(k)
- 保证每个位置被选为地雷的概率相等
易错点
- 每次都在整个数组范围内随机选下标
- 遍历方向和随机范围不匹配,导致偏差
- 用 rand() % n 引入偏差,不使用均匀分布
- 选 k 个时先完整洗牌,浪费时间
面试官常见追问
- 为什么每次在全范围随机交换是有偏的?
- 怎么从数据流中等概率选 k 个元素?
- 洗牌算法的随机数要注意什么?
- 洗牌的时间复杂度是多少?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 赛马问题:最少比赛场次19 场
- 判断点是否在三角形内(含边界)10 场
- 两个鸡蛋确定楼层9 场
- 小白鼠试毒(二进制编码)9 场
- 用一个随机数生成器等概率生成另一个范围8 场
- 十进制与其他进制的转换8 场
- 天平称球找出轻球的最少次数7 场
- 不使用临时变量交换两个数6 场
- 阶乘末尾有多少个 05 场
- 整数反转(LeetCode 7)5 场