LC380
常数时间插入、删除和获取随机元素
设计 · 数组+哈希可视化:设计题缓存O(1) 插入/删除/随机:getRandom 等概率返回 {1,2,3} 中任一。
时间 O(1) 各操作空间 O(n)
题目1 / 10
题目与输入建立输入、目标与算法心智
insert/delete/getRandom 均 O(1)
正在加载算法场景...
当前发生了什么
O(1) 插入/删除/随机:getRandom 等概率返回 {1,2,3} 中任一。
机器状态
nums 数组、val→idx map、长度。
为什么正确
数组存值、map(val→index);删时用末元素填坑再 pop。
不变量
map 与数组内容双向一致。
面试怎么说
数组+哈希:insert push;remove 用末尾覆盖并 pop;random 按 index 取,O(1) 全操作。
人类输入
O(1) 插入/删除/随机:getRandom 等概率返回 {1,2,3} 中任一。
机制
数组存值、map(val→index);删时用末元素填坑再 pop。
机器状态
nums 数组、val→idx map、长度。
可观察结果
remove(2) 后 getRandom 仍在 {1,3} 中等概率。
不变量
- · map 与数组内容双向一致。
常见误区
- · 删除中间元素时忘记把末尾换到被删位置。
迁移练习
- · LC146 LRU Cache
- · LC381 O(1) Random with Dup
面试怎么答
数组+哈希:insert push;remove 用末尾覆盖并 pop;random 按 index 取,O(1) 全操作。