面试题库 › C++ / 后端 › 洗牌算法(Fisher-Yates)与随机选取

洗牌算法(Fisher-Yates)与随机选取

难度 ★★☆在 11 场真实面经中被问到 方向:C++ / 后端考点:数学与智力题

哪些公司问过

网易互娱2多益网络2腾讯1cvte1百度1腾讯音乐1腾娱互动1多家公司(猿辅导、百度、网易互娱、滴滴、锐捷网络、吉比特、亿联网络等)1

常见岗位:C/C++ 软件开发、游戏研发、后端开发、C++ 后端、游戏客户端

答案要点

  1. Fisher-Yates:从后向前,对下标 i 在 [0, i] 随机选 j 并交换,O(n),原地
  2. 每种排列出现的概率相等,均为 1/n!
  3. 错误写法:每次在 [0, n-1] 随机选下标交换,结果有偏
  4. 扫雷选 k 个地雷:位置编号成一维数组,只做前 k 步洗牌,取前 k 个,O(k)
  5. 保证每个位置被选为地雷的概率相等

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题