原创数据结构设计哈希表约 2936 字大约 10 分钟
Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
380. Insert Delete GetRandom O(1) | 380. O(1) 时间插入、删除和获取随机元素 | 🟠 |
710. Random Pick with Blacklist | 710. 黑名单中的随机数 | 🔴 |
- | 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 | 🟠 |
本文讲两道比较有技巧性的数据结构设计题,都是和随机读取元素相关的,我在后文 谈谈游戏中的随机算法 也写过类似的问题。
这些问题的一个技巧点在于,如何结合哈希表和数组,使得数组的删除操作时间复杂度也变成 O(1)?下面来一道道看。