Insert Delete GetRandom O(1)

leetcode 380.

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Solution. To solve this problem, we need to use an ArrayList to maintain all the elements, and a HashMap to maintain the position of each element.

Every time when adding, just add in ArrayList and HashMap.
When getting the random, just get a random in ArrayList.
When removing, we delete in HashMap. If element is not in the last, we need to move the last element to the position of deleting element, and update the HashMap.

public class RandomizedSet {

    Map<Integer, Integer> loc;
    List<Integer> list;
    Random random = new Random();

    /** Initialize your data structure here. */
    public RandomizedSet() {
        loc = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (loc.containsKey(val)) {
            return false;
        }
        loc.put(val, list.size());
        list.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!loc.containsKey(val)) {
            return false;
        }
        int pos = loc.remove(val);
        int lastEle = list.remove(list.size() - 1);
        if (pos != list.size()) {
            list.set(pos, lastEle);
            loc.put(lastEle, pos);
        }
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

}

Check my code on github.