380. O(1) 时间插入、删除和获取随机元素

approach 1

class RandomizedSet {
    Map<Integer, Integer> map = new HashMap<>();
    List<Integer> list = new ArrayList<>();
    Random random = new Random();

    public RandomizedSet() {
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        Integer index = map.get(val);
        if (index != null) {
            int n = list.size();
            int last = list.get(n - 1);
            list.set(index.intValue(), last);
            list.remove(n - 1);
            map.put(last, index.intValue());
            map.remove(val);
            return true;
        }
        return false;

    }
    
    public int getRandom() {
        int r = random.nextInt(list.size());
        return list.get(r);
    }
}