 时间插入、删除和获取随机元素)
一、题目核心要求
需要实现三个操作，全部平均时间复杂度 O (1)：
insert(val)：插入元素，存在返回 false，不存在插入返回 trueremove(val)：删除元素，不存在返回 false，存在删除返回 truegetRandom()：随机等概率返回集合中一个元素
单独容器的缺陷
- ArrayList（动态数组）
- 尾部插入、随机访问 O (1)，完美满足
getRandom - 根据值查找、中间删除 O (n)，无法满足 O (1) 删除
- 尾部插入、随机访问 O (1)，完美满足
- 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; }流程：
- HashMap 判断元素是否存在，去重；
- 新元素直接追加到数组尾部（数组尾插 O (1)）；
- 哈希表记录该值的下标。
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; }关键步骤拆解：
- 拿到要删元素的下标
index； - 取出数组末尾元素
last； - 数组 index 位置覆盖为 last；
- 修改哈希表：last 对应的下标改为 index；
- 数组删掉最后一位（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)：
- index = 1，last = 7
- nums.set(1,7) → nums = [2,7,7]
- ind.put (7, 1) → 7 的下标更新为 1
- 删除数组末尾：nums = [2,7]
- ind 删除 key=5，最终
ind={2:0,7:1}
四、易错细节
- 删除时必须先更新末尾元素的下标映射，再删数据如果先
ind.remove(val)再更新 last 的下标，逻辑直接出错。 - 数组删除只能删末尾，不能删中间元素
nums.remove(index)是按下标删除中间元素，会移位 O (n)，绝对不能用。 - 插入时新元素下标是
nums.size()add 之前数组长度就是新元素的下标，add 后长度 + 1。 - 元素唯一，HashMap 天然去重，插入前必须判断
containsKey。 - getRandom 依赖数组长度，数组为空时题目保证不会调用。
五、时间复杂度总结
- insert：HashMap 存入 + 数组尾插 → O (1)
- remove：HashMap 查找 / 修改 / 删除 + 数组尾删 → O (1)
- getRandom：随机下标 + 数组下标访问 → O (1) 空间复杂度：O (n)，两个容器都存储全部元素。
六、代码优缺点
优点
- 完全满足题目 O (1) 要求，逻辑简洁；
- 删除交换尾部元素的优化是本题核心考点。
可优化小细节
- 变量命名可读性差：
ind→valToIndex； - Random 实例全局复用，无需重复创建，当前写法没问题；
- 泛型可规范书写，无语法错误。
七、核心考点总结
- 为什么不能只用 ArrayList / 只用 HashSet？ ArrayList 删除慢，HashSet 不支持随机下标访问；两者结合互补。
- 删除操作为什么要和最后一个元素交换？ 数组尾部删除是 O (1)，中间删除需要移动元素 O (n)，交换规避移位。
- HashMap 在本题的作用？ 快速根据数值找到对应数组下标，保证删除操作 O (1)。