380. Insert Delete GetRandom O(1)

class RandomizedSet {

    private final Map<Integer, Integer> map; // key 为值，value 为 list 中的索引
    private final List<Integer> list; // 存储的 val 值

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        this.map = new HashMap<>();
        this.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 (map.containsKey(val)) {
            return false;
        }

        map.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 (!map.containsKey(val)) {
            return false;
        }

        int removeIndex = map.get(val);

        // 将尾部元素移动至需要删除的元素对应的位置上
        int lastIndex = list.size() - 1;
        int lastVal = list.get(lastIndex);
        list.set(removeIndex, lastVal);
        map.put(lastVal, removeIndex); // 移动元素后不要忘记维护 map 中的索引
        list.remove(lastIndex);
        map.remove(val);
        return true;
    }

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

}

References

380. Insert Delete GetRandom O(1)