O(1) 时间插入、删除和获取随机元素(LeetCode 380)
哪些公司问过
答案要点
- 动态数组存元素支持O(1)随机访问,哈希表存值到下标的映射
- insert:已存在返回false,否则尾插并记录下标
- remove:用末尾元素覆盖被删位置并更新其下标,再弹出末尾、删除映射
- getRandom:在[0, size)内取随机下标,等概率返回
- 三个操作平均O(1),空间O(n)
易错点
- 在数组中间直接erase,删除退化为O(n)
- 先删映射再更新末尾元素下标,被删元素恰为末尾时会把它重新加回
- 忘记更新被移动元素在哈希表中的下标
面试官常见追问
- 允许重复元素(LeetCode 381)怎么改?
- 为什么不能只用哈希表?
- 用rand() % n有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。