# 0380. Insert Delete GetRandom O(1)
###### tags: `Leetcode` `Bloomberg` `FaceBook` `Design`
Link: https://leetcode.com/problems/insert-delete-getrandom-o1/
## 思路
用一个HashMap找到数字和它在list里面idx的对应
用一个List存所有的数字
这里最容易出错的地方是remove的时候，因为要保证删掉中间的一个的时候，其他数字的idx不变，因此要把最后一个挪到前面来
但要注意的是两个remove是最后做的，不然如果出现list里面只有一个元素的时候就会出错
## Code

class RandomizedSet {
    Map<Integer,Integer> valToIndex;
    List<Integer> values;
    Random rand;
    public RandomizedSet() {
        valToIndex = new HashMap<>();
        values = new ArrayList<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        if(valToIndex.containsKey(val)){
            return false;
        }
        else{
            values.add(val);
            valToIndex.put(val, values.size()-1);
            return true;
        }
    }
    
    public boolean remove(int val) {
        if(!valToIndex.containsKey(val)){
            return false;
        }
        else{
            int idx = valToIndex.get(val);
            int lastElement = values.get(values.size()-1);
            valToIndex.put(lastElement, idx);
            values.set(idx, lastElement);
            values.remove(values.size()-1);
            valToIndex.remove(val);
            return true;
        }
    }
    
    public int getRandom() {
        int selectIdx = rand.nextInt(values.size());
        return values.get(selectIdx);
    }
}