常数时间删除-查找数组中的任意元素

380. 常数时间插入、删除和获取随机元素 https://leetcode.cn/problems/insert-delete-getrandom-o1

380. Insert Delete GetRandom O(1) https://leetcode.com/problems/insert-delete-getrandom-o1

710. 黑名单中的随机数 https://leetcode.cn/problems/random-pick-with-blacklist

710. Random Pick with Blacklist https://leetcode.com/problems/random-pick-with-blacklist

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 https://leetcode.cn/problems/FortPu

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 https://leetcode.com/problems/FortPu

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
380. Insert Delete GetRandom O(1)	380. O(1) 时间插入、删除和获取随机元素	🟠
710. Random Pick with Blacklist	710. 黑名单中的随机数	🔴
-	剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器	🟠

前置知识

阅读本文前，你需要先学习：

• 数组基础
• 数组实现
• 哈希表基础
• 哈希表实现
• 用数组加强哈希表

本文讲两道比较有技巧性的数据结构设计题，都是和随机读取元素相关的，我在后文 谈谈游戏中的随机算法 也写过类似的问题。

这些问题的一个技巧点在于，如何结合哈希表和数组，使得数组的删除操作时间复杂度也变成 O(1)？下面来一道道看。

实现随机集合

避开黑名单的随机数

loading...