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

java 实现

class RandomizedSet {
            //需要hash map,list,random
    private Map<Integer, Integer> map; //存储list中的元素,值和索引
    private List<Integer> list;
    private Random random;

    public RandomizedSet() {
        map = new HashMap<>(); //存储list中的元素,值和索引
        list = new ArrayList<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)) {
            return false;
        }
        map.put(val, list.size());//由于list下标从0开始,所以可以用list.size()作为插入元素的索引下标
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if(!map.containsKey(val)) {
            return false;
        }
        //根据map获取待删除元素的下标
        int index = map.get(val);

        int LastElement = list.get(list.size() - 1);

        list.set(index, LastElement);//覆盖被删除的元素
        map.put(LastElement, index); //更新hashmap
        list.remove(list.size() - 1);

        map.remove(val);
        
        return true;

    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size())); // 方法 nextInt(n) 会生成一个范围为 [0, n) 的随机整数
    }
}