Implement the RandomizedSet class:
- RandomizedSet() Initializes the RandomizedSet object.
- bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
- bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
- int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
It's clear that it's a data structure. We need to implement a set and random method.
hash? unordered_set.
STD: only trick: we build a unordered_map to display value->position in the array; and array. both store the insert value.
when we need to delete the element. We need to swap the array's value and last of array and delete it in o(1);
It use the random property in array is in o(1).
AC!