How to Deleting Array Element in O(1) Time
OriginalAbout 4643 words
Info
English content is still improving...
You will not only learn the algorithm tricks, also resolve these LeetCode problems:
LeetCode | Difficulty |
---|---|
380. Insert Delete GetRandom O(1) | 🟠 |
710. Random Pick with Blacklist | 🔴 |
Prerequisite Knowledge
Before reading this article, you need to learn:
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.