380_Insert_Delete_GetRandom_O(1).java

classRandomizedSet {
privateList<Integer> list;
privateMap<Integer, Integer> hm;

/** Initialize your data structure here. */
publicRandomizedSet() {
list = newArrayList<>();
hm = newHashMap<>();
 }

/**
 * Inserts a value to the set. Returns true if the set did not already contain
 * the specified element.
 */
publicbooleaninsert(intval) {
if (hm.containsKey(val)) {
returnfalse;
 }

list.add(val);
hm.put(val, list.size() - 1);
returntrue;
 }

/**
 * Removes a value from the set. Returns true if the set contained the specified
 * element.
 */
publicbooleanremove(intval) {
if (!hm.containsKey(val)) {
returnfalse;
 }

intidx = hm.get(val);
intlastElement = list.get(list.size() - 1);

list.set(idx, lastElement);
list.remove(list.size() - 1);
hm.put(lastElement, idx);
hm.remove(val);

returntrue;
 }

/** Get a random element from the set. */
publicintgetRandom() {
Randomrand = newRandom();
intrandIdx = rand.nextInt(list.size());

returnlist.get(randIdx);
 }
}