生成不重复随机数
哪些公司问过
答案要点
- N 接近 M:Fisher-Yates 洗牌,从后往前与 [0, i] 随机位置交换,O(M)
- M 大 N 小:随机数加哈希集合去重,期望 O(N),避免线性扫描
- 1 亿个 int 约 400MB;位图只需 12.5MB,但后期冲突增多
- 惰性洗牌:哈希表只记录被交换过的位置,每次 O(1)
- 内存和已取个数成正比,适合在线逐个生成
易错点
- 每次生成后线性扫描判重,复杂度 O(N²)
- 洗牌时和整个数组随机交换,导致分布不均匀
面试官常见追问
- 为什么 Fisher-Yates 是均匀的?
- 如果连哈希表的内存都不想花,怎么办?
- 怎么从数据流中等概率随机抽 k 个?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。