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

• 实现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 。

思路

我第一次看到这个题目也是很蒙，下面思考一下：

1. 数据结构选择背景

• 需要实现一个数据结构，支持O(1)时间复杂度的插入、删除和随机访问。
• 数组：随机访问O(1)，但直接删除中间元素需移动后续元素（O(n)）。
• 链表：插入/删除O(1)，但随机访问需要遍历（O(n)）。
• 哈希表：快速查找元素是否存在（O(1)）。

2.数组+哈希表的结合策略

数组存储实际元素，保证随机访问时可通过索引直接定位。
哈希表维护值→索引的映射，解决删除时定位元素的问题。

图解

3. 删除优化：

当删除元素时，将数组最后一个元素覆盖到待删位置，更新哈希表，避免移动元素。

int loc = mp.remove(val);         // 获取被删元素的位置
if (loc != idx) {                 // 如果被删元素不是最后一个
    nums[loc] = nums[idx];        // 用末尾元素覆盖被删位置
    mp.put(nums[idx], loc);       // 更新末尾元素的索引
}
idx--;                            // 缩小有效数组范围

变量解释

• val：需要从数组中删除的元素值。
• mp：一个HashMap<Integer, Integer>，用于存储数组元素到其索引的映射（元素值 → 索引位置）。
• nums：动态数组，存储实际元素。
• idx：当前数组的有效元素数量（同时也是最后一个元素的索引）。
• mp.put的目的：在移动元素后，更新哈希表中元素的新索引，确保映射关系的正确性。
• mp.remove的作用：删除元素的映射，并获取其原索引，用于后续的元素移动操作。

为什么数组大小设为20000

• 预分配固定内存：避免动态扩容（如ArrayList的扩容会触发复制，导致均摊O(1)但实际波动）。
• 题目约束：可能题目要求最多插入20000次，或测试数据保证元素量不超过此值。
• 空间换时间：牺牲固定内存换取所有操作严格O(1)时间。

链表+哈希表的缺陷

• 无法快速按索引访问：
  链表需要遍历才能到达指定索引，导致getRandom()退化为O(n)。
• 维护成本高：
  需额外维护双向链表以保证删除操作O(1)，代码复杂度增加。
  关键设计总结
• 数组紧凑性：通过用末尾元素覆盖被删位置，始终保持数组前idx+1位有效。
  哈希表同步更新：每次插入/删除都需更新哈希表，保证索引映射的准确性。
  随机访问优化：直接通过random.nextInt(idx+1)生成随机索引，利用数组的O(1)访问。

题解

class RandomizedSet {
    static int[] nums=new int[200000];
    Random random=new Random();
    Map<Integer,Integer> mp=new HashMap<>();
    int idx=-1;
    public RandomizedSet() {
        
    }
    public boolean insert(int val) {
        if(mp.containsKey(val))
        {
            return false;
        }
        nums[++idx]=val;
        mp.put(val,idx);
        return true;
        
    }
    
    public boolean remove(int val) {
        if(!mp.containsKey(val))
        {
            return false;
        }
        int loc=mp.remove(val);
        if(loc!=idx) mp.put(nums[idx],loc);
        nums[loc]=nums[idx -- ];
        return true;
    }
    
    public int getRandom() {
        return nums[random.nextInt(idx+1)];
    }
}