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

leetcode380题

本题的难点在于：
1.插入、删除、获取随机元素这三个操作的时间复杂度都是O（1）。
2.获取随机元素必须是等概率返回随机元素。

我们先来分析一下：对于插入、删除、查找这几个操作时间复杂度O（1），可以通过HashSet实现，但我们不能在O（1）的时间内获取随机元素，且Set集合具有数据的唯一性。

怎样在O（1）的时间内获取随机元素呢？

我们能够想到的数据结构只有数组，但如果⽤数组存储元素的话，插⼊，删除的时间复杂度怎么可能是 O(1) 呢？

可以做到！对数组尾部进⾏插⼊和删除操作不会涉及数据搬移，时间复杂度是 O(1)。

所以，如果我们想在 O(1) 的时间删除数组中的某⼀个元素 val，可以先把这个元素交换到数组的尾部，然后再 pop 掉。

交换两个元素必须通过索引进⾏交换对吧，那么我们需要⼀个哈希表 valToIndex 来记录每个元素值对应的索引。

```Java
class RandomizedSet {
    List nums;
    HashMap valToIndex;

    public RandomizedSet() {
        nums=new ArrayList<>();
        valToIndex=new HashMap<>();
    }

    public boolean insert(int val) {
        if(nums.contains(val)){
            return false;
        }
        //不存在，插入nums的尾部
        //记录val对应的索引值
        valToIndex.put(val,nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if(!nums.contains(val)){
            return false;
        }//不存在不需要删除
        //存在，先拿到val对应的索引
        int index=valToIndex.get(val);
        //修改最后一个元素的索引
        valToIndex.put(nums.get(nums.size()-1),index);
        //交换val和最后一个元素,删除最后一个元素
        nums.set(index,nums.get(nums.size()-1));
        nums.remove(nums.size()-1);
        //删除val对应的索引
        valToIndex.remove(val);
        return true;
    }

    public int getRandom() {
        return nums.get((int) (Math.random()*nums.size()));

    }
}
```