[LeetCode][380. Insert Delete GetRandom O(1)] Data Structures: Thought Process from HashMap to HashMap + Array
By Long Luo
This article is the solution Data Structures: Thought Process from HashMap to HashMap + Array of Problem 380. Insert Delete GetRandom O(1).
Intuition
It’s easy to think of using a Hash Table to achieve time complexity for and operations. However, we need time complexity to complete the operation.
The Array structure can complete the operation of obtaining random elements in time complexity, but it can’t completed the and operations in time complexity.
So How?
Aha!!!
We can combining the and Array. The Array stores the elements, and the stores the input value as the and the array subscript as the value.
We need to apply for an array nums of sufficient size (the data range is ), and a variable to record how many space is currently used.
-
: Judge whether the contains the , if not, insert the to the and update the Array nums.
-
: Judge whether the contains the , if not, get the location loc of the input val, replace the loc with the last value of the array, remove the from and update the .
-
: Just select a subscript at random and return the element of the array.
1 | class RandomizedSet { |
Analysis
- Time Complexity: .
- Space Complexity: .
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗