面试题库 › C++ / 后端 › 生成不重复随机数

生成不重复随机数

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

哪些公司问过

淘天1网易互娱1游卡1

常见岗位:C++ 后端、游戏服务端、测试开发

答案要点

  1. N 接近 M:Fisher-Yates 洗牌,从后往前与 [0, i] 随机位置交换,O(M)
  2. M 大 N 小:随机数加哈希集合去重,期望 O(N),避免线性扫描
  3. 1 亿个 int 约 400MB;位图只需 12.5MB,但后期冲突增多
  4. 惰性洗牌:哈希表只记录被交换过的位置,每次 O(1)
  5. 内存和已取个数成正比,适合在线逐个生成

易错点

面试官常见追问

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

相关面试题