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

一、题目核心要求需要实现三个操作全部平均时间复杂度 O (1)insert(val)插入元素存在返回 false不存在插入返回 trueremove(val)删除元素不存在返回 false存在删除返回 truegetRandom()随机等概率返回集合中一个元素单独容器的缺陷ArrayList动态数组尾部插入、随机访问 O (1)完美满足getRandom根据值查找、中间删除 O (n)无法满足 O (1) 删除HashMap/HashSet插入、删除、查找 O (1)不支持随机下标访问无法快速随机取元素核心解题思路双容器配合ArrayList nums存放所有数值依靠下标实现随机取值HashMap indkey 数值value 该数值在数组中的下标实现 O (1) 查找下标 两者互补全部操作做到平均 O (1)。二、代码逐段逻辑解析成员变量javaListInteger nums; // 存储所有元素用于随机访问 MapInteger,Integer ind; // 值 - 数组下标映射 Random random; // 生成随机下标构造方法初始化数组、哈希表、随机数工具。1. insert 插入逻辑javapublic boolean insert(int val) { if(ind.containsKey(val)){ return false; // 已存在插入失败 } int indexnums.size(); // 新元素放在数组末尾 nums.add(val); ind.put(val,index); // 记录值对应的下标 return true; }流程HashMap 判断元素是否存在去重新元素直接追加到数组尾部数组尾插 O (1)哈希表记录该值的下标。2. remove 删除数组中间删除会导致后续元素前移时间 O (n)优化技巧把待删除元素和数组最后一个元素交换再删除数组末尾数组尾删 O (1)。javapublic boolean remove(int val) { if(!ind.containsKey(val)){ return false; } // 1. 获取待删除元素下标 int indexind.get(val); // 2. 获取数组最后一个元素 int lastnums.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)哈希表删掉 val3. getRandom 随机取值javapublic int getRandom() { int ranrandom.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 1last 7nums.set(1,7) → nums [2,7,7]ind.put (7, 1) → 7 的下标更新为 1删除数组末尾nums [2,7]ind 删除 key5最终ind{2:0,7:1}四、易错细节删除时必须先更新末尾元素的下标映射再删数据如果先ind.remove(val)再更新 last 的下标逻辑直接出错。数组删除只能删末尾不能删中间元素nums.remove(index)是按下标删除中间元素会移位 O (n)绝对不能用。插入时新元素下标是nums.size()add 之前数组长度就是新元素的下标add 后长度 1。元素唯一HashMap 天然去重插入前必须判断containsKey。getRandom 依赖数组长度数组为空时题目保证不会调用。五、时间复杂度总结insertHashMap 存入 数组尾插 → O (1)removeHashMap 查找 / 修改 / 删除 数组尾删 → O (1)getRandom随机下标 数组下标访问 → O (1) 空间复杂度O (n)两个容器都存储全部元素。六、代码优缺点优点完全满足题目 O (1) 要求逻辑简洁删除交换尾部元素的优化是本题核心考点。可优化小细节变量命名可读性差ind→valToIndexRandom 实例全局复用无需重复创建当前写法没问题泛型可规范书写无语法错误。七、核心考点总结为什么不能只用 ArrayList / 只用 HashSet ArrayList 删除慢HashSet 不支持随机下标访问两者结合互补。删除操作为什么要和最后一个元素交换 数组尾部删除是 O (1)中间删除需要移动元素 O (n)交换规避移位。HashMap 在本题的作用 快速根据数值找到对应数组下标保证删除操作 O (1)。