Implement RandomizedSet that supports insert, remove, and getRandom in O(1) average time. getRandom returns a random element with equal probability.
insert(1)→true, remove(2)→false, insert(2)→true, getRandom()→1or2, remove(1)→true, insert(2)→false, getRandom()→2
Use a HashMap (val→index) and a List (for O(1) random access). On remove, swap with last element.
- Map map; List list.
- insert: if not in map, add to list, map[val]=list.size()-1.
- remove: if in map, swap val with last element (update last element's map entry), remove from list and map.
- getRandom: return list[random index].
import java.util.*;
class RandomizedSet {
Map<Integer,Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
Random rand = new Random();
public boolean insert(int val) {
if (map.containsKey(val)) return false;
list.add(val); map.put(val, list.size()-1); return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) return false;
int idx = map.get(val), last = list.get(list.size()-1);
list.set(idx, last); map.put(last, idx);
list.remove(list.size()-1); map.remove(val); return true;
}
public int getRandom() { return list.get(rand.nextInt(list.size())); }
}
- Time Complexity: All operations O(1) average
- Space Complexity: O(N)