Description
Implement the RandomizedSet class with insert, remove, and getRandom methods, all with average O(1) time complexity.
Examples
Input:
["insert",1],["remove",2],["insert",2],["getRandom"],["remove",1]Output:
[true,false,true,2,true]Explanation:
Operations on the set.
Input:
input = [[1],[2]]Output:
trueExplanation:
For input = [[1],[2]], the answer is true because the insert delete getrandom o(1) condition is satisfied.
Input:
[["insert",5],["insert",3],["getRandom"],["insert",5],["remove",3],["getRandom"],["remove",5]]Output:
[true,true,3,false,true,5,true]Explanation:
Insert 5 (success), insert 3 (success), getRandom returns 3 (could be 3 or 5), insert 5 again (fails, already exists), remove 3 (success), getRandom returns 5 (only element left), remove 5 (success)
Constraints
- •
-2³¹ ≤ val ≤ 2³¹ - 1 - •
At most 2 * 10⁵ calls to insert, remove, and getRandom