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

难度 ： 简单 | 中等√ | 困难 ------------------- 用时：18分钟（第一次） ------------------- 作题日期：2023-12-03
ps: 本人理解有限，以下是自我理解，官方和大佬有更完整和详细的解析！！！

题目描述

• 题目描述

  实现RandomizedSet 类：
  
  RandomizedSet() 初始化 RandomizedSet 对象
  bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
  你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
  

• 案例演示

  示例：
  
  输入
  ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
  [[], [1], [2], [2], [], [1], [2], []]
  输出
  [null, true, false, true, 2, true, false, 2]
  
  解释
  RandomizedSet randomizedSet = new RandomizedSet();
  randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
  randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
  randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
  randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
  randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
  randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
  randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
  
  

• 提示

  -231 <= val <= 231 - 1
  最多调用 insert、remove 和 getRandom 函数 2 * 105 次
  在调用 getRandom 方法时，数据结构中 至少存在一个 元素。
  

代码及解析

暴力解法

利用linkedList的特性和Math类中的random设计出该类，用时稍微较长，但是过了（苦笑）

class RandomizedSet {
    private List<Integer> list = new LinkedList();
    public RandomizedSet() {

    }
    
    public boolean insert(int val) {
        int indexOf = list.indexOf(val);
        if(indexOf != -1){
            return false;
        }
        boolean b = list.add(val);
        return b;
    }
    
    public boolean remove(int val) {
        int indexOf = list.indexOf(val);
        if(indexOf ==-1){
            return false;
        }
     Integer rem = list.remove(indexOf);
       return true;
    }
    
    public int getRandom() {
        int size = list.size();
        double f = Math.random()/Math.nextDown(1.0);
        int x = (int) (0*(1.0 - f) + size*f);
        Integer integer = list.get(x);
        return integer;
    }
}

看完官方题解后的理解

利用变长数组和哈希表进行设计

class RandomizedSet2{
    List<Integer> list;
    Map<Integer,Integer> indxMap;
    Random random ;
    public RandomizedSet2() {
        this.list = new ArrayList<Integer>();
        this.indxMap = new HashMap<>();
        this.random = new Random();
    }
    
    public boolean insert(int val) {
        //判断val是否已经存在
        if(indxMap.containsKey(val)){
            return false;
        }
        int index = list.size();
        //存入变长数组
        list.add(val);
        //存入哈希表(数值，在变长数组中的位置)
        indxMap.put(val, index);
        
        return true;
    }
    
    public boolean remove(int val) {
        //判断是否存在在哈希表中
        if(!indxMap.containsKey(val)){
            return false;
        }
        //利用最后一个元素覆盖删除的元素，同时，删除最后一个元素
        int index = indxMap.get(val);
        int last = list.get(list.size() - 1);
        list.set(index, last);
        indxMap.put(last, index);
        list.remove(list.size() - 1);
        indxMap.remove(val);
        return true;
    }
    
    public int getRandom() {
        //生成随机索引
        int nextInt = random.nextInt(list.size());
        //获取索引的值
        Integer integer = list.get(nextInt);
        return integer;
    }
}