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

一、题目核心要求

需要实现三个操作，全部平均时间复杂度 O (1)：

1. insert(val)：插入元素，存在返回 false，不存在插入返回 true
2. remove(val)：删除元素，不存在返回 false，存在删除返回 true
3. getRandom()：随机等概率返回集合中一个元素

单独容器的缺陷

1. ArrayList（动态数组）
   • 尾部插入、随机访问 O (1)，完美满足getRandom
   • 根据值查找、中间删除 O (n)，无法满足 O (1) 删除
2. HashMap/HashSet
   • 插入、删除、查找 O (1)
   • 不支持随机下标访问，无法快速随机取元素

核心解题思路：双容器配合

• ArrayList nums：存放所有数值，依靠下标实现随机取值
• HashMap ind：key = 数值，value = 该数值在数组中的下标，实现 O (1) 查找下标 两者互补，全部操作做到平均 O (1)。

二、代码逐段逻辑解析

成员变量

java

List<Integer> nums; // 存储所有元素，用于随机访问 Map<Integer,Integer> ind; // 值 -> 数组下标映射 Random random; // 生成随机下标

构造方法

初始化数组、哈希表、随机数工具。

1. insert 插入逻辑

java

public boolean insert(int val) { if(ind.containsKey(val)){ return false; // 已存在，插入失败 } int index=nums.size(); // 新元素放在数组末尾 nums.add(val); ind.put(val,index); // 记录值对应的下标 return true; }

流程：

1. HashMap 判断元素是否存在，去重；
2. 新元素直接追加到数组尾部（数组尾插 O (1)）；
3. 哈希表记录该值的下标。

2. remove 删除

数组中间删除会导致后续元素前移，时间 O (n)，优化技巧：把待删除元素和数组最后一个元素交换，再删除数组末尾，数组尾删 O (1)。

java

public boolean remove(int val) { if(!ind.containsKey(val)){ return false; } // 1. 获取待删除元素下标 int index=ind.get(val); // 2. 获取数组最后一个元素 int last=nums.get(nums.size()-1); // 3. 覆盖待删除位置 nums.set(index,last); // 4. 更新最后一个元素的下标映射 ind.put(last, index); // 5. 删除数组末尾、删除哈希表中val记录 nums.remove(nums.size()-1); ind.remove(val); return true; }

关键步骤拆解：

1. 拿到要删元素的下标index；
2. 取出数组末尾元素last；
3. 数组 index 位置覆盖为 last；
4. 修改哈希表：last 对应的下标改为 index；
5. 数组删掉最后一位（O (1)），哈希表删掉 val；

3. getRandom 随机取值

java

public int getRandom() { int ran=random.nextInt(nums.size()); return nums.get(ran); }

random.nextInt(n)生成[0, n-1]均匀随机下标，数组按下标访问 O (1)，每个元素等概率。

三、完整执行示例

初始：nums = [2,5,7]，ind={2:0,5:1,7:2}执行remove(5)：

1. index = 1，last = 7
2. nums.set(1,7) → nums = [2,7,7]
3. ind.put (7, 1) → 7 的下标更新为 1
4. 删除数组末尾：nums = [2,7]
5. ind 删除 key=5，最终ind={2:0,7:1}

四、易错细节

1. 删除时必须先更新末尾元素的下标映射，再删数据如果先ind.remove(val)再更新 last 的下标，逻辑直接出错。
2. 数组删除只能删末尾，不能删中间元素nums.remove(index)是按下标删除中间元素，会移位 O (n)，绝对不能用。
3. 插入时新元素下标是nums.size()add 之前数组长度就是新元素的下标，add 后长度 + 1。
4. 元素唯一，HashMap 天然去重，插入前必须判断containsKey。
5. getRandom 依赖数组长度，数组为空时题目保证不会调用。

五、时间复杂度总结

• insert：HashMap 存入 + 数组尾插 → O (1)
• remove：HashMap 查找 / 修改 / 删除 + 数组尾删 → O (1)
• getRandom：随机下标 + 数组下标访问 → O (1) 空间复杂度：O (n)，两个容器都存储全部元素。

六、代码优缺点

优点

1. 完全满足题目 O (1) 要求，逻辑简洁；
2. 删除交换尾部元素的优化是本题核心考点。

可优化小细节

1. 变量命名可读性差：ind→valToIndex；
2. Random 实例全局复用，无需重复创建，当前写法没问题；
3. 泛型可规范书写，无语法错误。

七、核心考点总结

1. 为什么不能只用 ArrayList / 只用 HashSet？ ArrayList 删除慢，HashSet 不支持随机下标访问；两者结合互补。
2. 删除操作为什么要和最后一个元素交换？ 数组尾部删除是 O (1)，中间删除需要移动元素 O (n)，交换规避移位。
3. HashMap 在本题的作用？ 快速根据数值找到对应数组下标，保证删除操作 O (1)。