数组随机打乱:Fisher-Yates 洗牌
哪些公司问过
答案要点
- Fisher-Yates:从后往前,对下标 i 在 [0, i] 随机选 j 交换
- 每种排列等概率(1/n!),时间 O(n),空间 O(1)
- 错误写法:每次在 [0, n-1] 选下标交换,结果有偏
- 随机数范围要正确,如 rand() % (i+1),更好用均匀分布发生器
- 要求输出与输入不同时,洗牌后检查,相同则重洗
易错点
- 每次都在整个数组范围随机交换
- 随机数范围写错,造成偏差
- 用 rand() 取模,不注意均匀性
- 没有保证输出与输入不同的要求
面试官常见追问
- 洗完牌发给四个人,要让第二个人的胜率达到某个值怎么办?
- 为什么每次在整个范围随机交换是有偏的?
- 用随机数当键排序可以吗?
- 如何从数据流中等概率抽取 k 个元素?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场