1、前言

题目描述

2、思路

将最后一个元素放到移除元素的位置上，然后把最后一个元素删除就行，还要考虑最后一个是第一个情况

3、代码

class RandomizedSet {

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

    public RandomizedSet() {

    }

    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);

        return true;
    }

    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);
        list.remove(lastIndex);
        map.remove(val);

        return true;
    }

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

}