常数时间删除/查找数组中的任意元素
原创约 3710 字
本文讲解的例题
LeetCode | 力扣 | 难度 |
---|---|---|
710. Random Pick with Blacklist | 710. 黑名单中的随机数 | 🔴 |
380. Insert Delete GetRandom O(1) | 380. O(1) 时间插入、删除和获取随机元素 | 🟠 |
本文讲两道比较有技巧性的数据结构设计题,都是和随机读取元素相关的,我在后文 谈谈游戏中的随机算法 也写过类似的问题。
这些问题的一个技巧点在于,如何结合哈希表和数组,使得数组的删除操作时间复杂度也变成 O(1)?下面来一道道看。