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

380. O(1) 时间插入、删除和获取随机元素 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	Difficulty
380. Insert Delete GetRandom O(1)	🟠
710. Random Pick with Blacklist	🔴

Prerequisite Knowledge

Before reading this article, you need to learn:

• Array Basics
• Array Implementation
• Hash Table Basics
• Hash Table Implementation
• Enhancing Hash Tables with Arrays

This article discusses two data structure design problems that involve some clever techniques, both related to random element retrieval. I have also written about similar issues in the previous article Random Algorithms in Games.

One key point in these problems is how to combine hash tables and arrays so that the time complexity of the delete operation in the array also becomes O(1). Let's go through these problems one by one.

Implement Randomized Set

Random Numbers Avoiding a Blacklist

loading...