LeetCode 380 题解用哈希表 动态数组实现 O(1) 复杂度的 Insert Delete GetRandomRandomizedSet 设计模式【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南基于 LeetCode 题解仓库中的 insert-delete-getrandom-o1 题解文档系统讲解经典面试题「Insert Delete GetRandom O(1)」的两种解法纯哈希表方案与哈希表 动态数组swap-and-pop方案。读完本文你将掌握如何设计一个插入、删除、随机取值三项操作全部为 O(1) 平均复杂度的数据结构 RandomizedSet并理解 hash map 与 dynamic array 组合这一高频设计模式在真实工程中的落地写法。前置知识三种必备数据结构功底在动手实现之前需要先确认自己具备以下三项基础能力这也是本仓库题解文档明确的 PrerequisitesHash Maps哈希表理解 O(1) 平均时间复杂度的插入、删除、查找操作。这是本问题前两个需求insert/remove的自然选择。Dynamic Arrays动态数组理解数组如何支持 O(1) 随机访问以及 O(1) 均摊amortized的尾部追加与尾部弹出append/pop。这是实现getRandom()的关键载体。Swap-and-Pop Technique交换并弹出技巧知道如何通过对无序集合将要删除的元素与最后一个元素交换再从尾部弹出来达成 O(1) 删除。这是本问题的灵魂技巧。仓库中对应的题目源码位于 cpp/0380-insert-delete-getrandom-o1.cpp、java/0380-insert-delete-getrandom-o1.java、python/0380-insert-delete-getrandom-o1.py 等路径下文将逐一对照。题目需求回顾设计一个数据结构RandomizedSet支持以下三种操作且每种操作的平均时间复杂度都要求为 O(1)insert(val)向集合中插入元素。若val已存在返回false否则插入并返回true。remove(val)从集合中移除元素。若val不存在返回false否则移除并返回true。getRandom()等概率地随机返回集合中的任意一个元素。注意集合中的每个元素被返回的概率必须相等。三个需求单独看都不难难在同时满足哈希表擅长前两个却天然不支持按索引随机访问数组擅长随机访问却做不到 O(1) 的任意位置删除。下面两种解法正是围绕这一矛盾展开。解法一纯哈希表方案getRandom 退化为 O(n)核心直觉哈希表为插入和删除提供了 O(1) 平均时间因此第一个想法是只用一个哈希表搞定前两个需求。但哈希表不支持按下标随机访问——getRandom()需要随机挑一个元素而迭代到随机位置是 O(n) 的操作。因此本方案的做法是把哈希表的 keys 转换成列表再随机取一个下标。这是一种用getRandom()的性能换取实现简单性的方案。它虽然不符合题目的完整要求但作为演进到最优解的前置理解非常有价值。算法步骤初始化一个哈希表numMap和一个大小计数器size。insert(val)若val已存在于 map返回false否则将其加入 map值随意这里统一记 1size加一返回true。remove(val)若val不存在于 map返回false否则从 map 中删除size减一返回true。getRandom()在0到size - 1之间生成随机下标把 map 的 keys 转为列表返回该下标处的元素。多语言实现class RandomizedSet: def __init__(self): self.numMap {} self.size 0 def insert(self, val: int) - bool: if val in self.numMap: return False self.numMap[val] 1 self.size 1 return True def remove(self, val: int) - bool: if val not in self.numMap: return False del self.numMap[val] self.size - 1 return True def getRandom(self) - int: idx random.randint(0, self.size - 1) return list(self.numMap.keys())[idx]public class RandomizedSet { private HashMapInteger, Integer numMap; private int size; public RandomizedSet() { numMap new HashMap(); size 0; } public boolean insert(int val) { if (numMap.containsKey(val)) { return false; } numMap.put(val, 1); size; return true; } public boolean remove(int val) { if (!numMap.containsKey(val)) { return false; } numMap.remove(val); size--; return true; } public int getRandom() { int idx new Random().nextInt(size); IteratorInteger it numMap.keySet().iterator(); while (idx-- 0) { it.next(); } return it.next(); } }class RandomizedSet { private: unordered_mapint, int numMap; int size; public: RandomizedSet() : size(0) {} bool insert(int val) { if (numMap.count(val)) return false; numMap[val] 1; size; return true; } bool remove(int val) { if (!numMap.count(val)) return false; numMap.erase(val); size--; return true; } int getRandom() { int idx rand() % size; auto it numMap.begin(); advance(it, idx); return it-first; } };class RandomizedSet { constructor() { this.numMap new Map(); this.size 0; } /** * param {number} val * return {boolean} */ insert(val) { if (this.numMap.has(val)) return false; this.numMap.set(val, 1); this.size; return true; } /** * param {number} val * return {boolean} */ remove(val) { if (!this.numMap.has(val)) return false; this.numMap.delete(val); this.size--; return true; } /** * return {number} */ getRandom() { const keys Array.from(this.numMap.keys()); const idx Math.floor(Math.random() * this.size); return keys[idx]; } }public class RandomizedSet { private Dictionaryint, int numMap; private int size; private Random rand; public RandomizedSet() { numMap new Dictionaryint, int(); size 0; rand new Random(); } public bool Insert(int val) { if (numMap.ContainsKey(val)) { return false; } numMap[val] 1; size; return true; } public bool Remove(int val) { if (!numMap.ContainsKey(val)) { return false; } numMap.Remove(val); size--; return true; } public int GetRandom() { int idx rand.Next(0, size); var keys numMap.Keys.ToList(); return keys[idx]; } }type RandomizedSet struct { numMap map[int]int size int } func Constructor() RandomizedSet { return RandomizedSet{ numMap: make(map[int]int), size: 0, } } func (this *RandomizedSet) Insert(val int) bool { if _, exists : this.numMap[val]; exists { return false } this.numMap[val] 1 this.size return true } func (this *RandomizedSet) Remove(val int) bool { if _, exists : this.numMap[val]; !exists { return false } delete(this.numMap, val) this.size-- return true } func (this *RandomizedSet) GetRandom() int { idx : rand.Intn(this.size) for key : range this.numMap { if idx 0 { return key } idx-- } return 0 }class RandomizedSet() { private val numMap HashMapInt, Int() private var size 0 fun insert(val: Int): Boolean { if (numMap.containsKey(val)) { return false } numMap[val] 1 size return true } fun remove(val: Int): Boolean { if (!numMap.containsKey(val)) { return false } numMap.remove(val) size-- return true } fun getRandom(): Int { val idx (0 until size).random() return numMap.keys.elementAt(idx) } }class RandomizedSet { private var numMap: [Int: Int] private var size: Int init() { numMap [:] size 0 } func insert(_ val: Int) - Bool { if numMap[val] ! nil { return false } numMap[val] 1 size 1 return true } func remove(_ val: Int) - Bool { if numMap[val] nil { return false } numMap.removeValue(forKey: val) size - 1 return true } func getRandom() - Int { let idx Int.random(in: 0..size) return Array(numMap.keys)[idx] } }use rand::Rng; struct RandomizedSet { num_map: HashMapi32, i32, size: usize, } impl RandomizedSet { fn new() - Self { RandomizedSet { num_map: HashMap::new(), size: 0, } } fn insert(mut self, val: i32) - bool { if self.num_map.contains_key(val) { return false; } self.num_map.insert(val, 1); self.size 1; true } fn remove(mut self, val: i32) - bool { if !self.num_map.contains_key(val) { return false; } self.num_map.remove(val); self.size - 1; true } fn get_random(self) - i32 { let idx rand::thread_rng().gen_range(0..self.size); *self.num_map.keys().nth(idx).unwrap() } }复杂度分析时间复杂度getRandom()为 O(n)需要把 keys 转成列表或迭代到随机位置其余操作为 O(1)。空间复杂度O(n)其中 n 为集合中元素个数。解法二哈希表 动态数组全部操作 O(1)核心直觉要让包括getRandom()在内的所有操作都达到 O(1)需要把哈希表和动态数组组合起来数组nums真正存储值提供 O(1) 随机访问能力哈希表numMap记录每个值在数组中的下标value → index提供 O(1) 查找能力。难点在删除从数组中间删除元素是 O(n) 的。解决方法是swap-and-pop——把待删除元素与数组最后一个元素交换然后从尾部弹出整个过程 O(1)。这个交换并弹出技巧是处理无序集合 O(1) 删除的通用模式在本题之外也广泛适用于各种需要随机访问 快速删除的场景如洗牌算法、LRU 变体、推荐系统中的候选池剔除等。算法步骤初始化哈希表numMapvalue → index和列表nums。insert(val)若val已存在返回false否则把val追加到列表末尾并把其下标记入 map返回true。remove(val)若val不存在返回false取出val的下标idx将列表最后一个元素last覆盖到nums[idx]更新last在 map 中的下标为idx然后pop掉列表末尾最后从 map 中删除val返回true。getRandom()在0到nums.length - 1之间随机取一个下标直接返回nums中对应元素。多语言实现class RandomizedSet: def __init__(self): self.numMap {} self.nums [] def insert(self, val: int) - bool: if val in self.numMap: return False self.numMap[val] len(self.nums) self.nums.append(val) return True def remove(self, val: int) - bool: if val not in self.numMap: return False idx self.numMap[val] last self.nums[-1] self.nums[idx] last self.numMap[last] idx self.nums.pop() del self.numMap[val] return True def getRandom(self) - int: return random.choice(self.nums)public class RandomizedSet { private MapInteger, Integer numMap; private ListInteger nums; private Random rand; public RandomizedSet() { numMap new HashMap(); nums new ArrayList(); rand new Random(); } public boolean insert(int val) { if (numMap.containsKey(val)) return false; numMap.put(val, nums.size()); nums.add(val); return true; } public boolean remove(int val) { if (!numMap.containsKey(val)) return false; int idx numMap.get(val); int last nums.get(nums.size() - 1); nums.set(idx, last); numMap.put(last, idx); nums.remove(nums.size() - 1); numMap.remove(val); return true; } public int getRandom() { return nums.get(rand.nextInt(nums.size())); } }class RandomizedSet { private: unordered_mapint, int numMap; vectorint nums; public: RandomizedSet() {} bool insert(int val) { if (numMap.count(val)) return false; numMap[val] nums.size(); nums.push_back(val); return true; } bool remove(int val) { if (!numMap.count(val)) return false; int idx numMap[val]; int last nums.back(); nums[idx] last; numMap[last] idx; nums.pop_back(); numMap.erase(val); return true; } int getRandom() { return nums[rand() % nums.size()]; } };class RandomizedSet { constructor() { this.numMap new Map(); this.nums []; } /** * param {number} val * return {boolean} */ insert(val) { if (this.numMap.has(val)) return false; this.numMap.set(val, this.nums.length); this.nums.push(val); return true; } /** * param {number} val * return {boolean} */ remove(val) { if (!this.numMap.has(val)) return false; const idx this.numMap.get(val); const last this.nums[this.nums.length - 1]; this.nums[idx] last; this.numMap.set(last, idx); this.nums.pop(); this.numMap.delete(val); return true; } /** * return {number} */ getRandom() { return this.nums[Math.floor(Math.random() * this.nums.length)]; } }public class RandomizedSet { private Dictionaryint, int numMap; private Listint nums; private Random rand; public RandomizedSet() { numMap new Dictionaryint, int(); nums new Listint(); rand new Random(); } public bool Insert(int val) { if (numMap.ContainsKey(val)) { return false; } numMap[val] nums.Count; nums.Add(val); return true; } public bool Remove(int val) { if (!numMap.ContainsKey(val)) { return false; } int idx numMap[val]; int last nums[nums.Count - 1]; nums[idx] last; numMap[last] idx; nums.RemoveAt(nums.Count - 1); numMap.Remove(val); return true; } public int GetRandom() { int index rand.Next(nums.Count); return nums[index]; } }type RandomizedSet struct { numMap map[int]int nums []int } func Constructor() RandomizedSet { return RandomizedSet{ numMap: make(map[int]int), nums: []int{}, } } func (this *RandomizedSet) Insert(val int) bool { if _, exists : this.numMap[val]; exists { return false } this.numMap[val] len(this.nums) this.nums append(this.nums, val) return true } func (this *RandomizedSet) Remove(val int) bool { if _, exists : this.numMap[val]; !exists { return false } idx : this.numMap[val] last : this.nums[len(this.nums)-1] this.nums[idx] last this.numMap[last] idx this.nums this.nums[:len(this.nums)-1] delete(this.numMap, val) return true } func (this *RandomizedSet) GetRandom() int { return this.nums[rand.Intn(len(this.nums))] }class RandomizedSet() { private val numMap HashMapInt, Int() private val nums ArrayListInt() fun insert(val: Int): Boolean { if (numMap.containsKey(val)) { return false } numMap[val] nums.size nums.add(val) return true } fun remove(val: Int): Boolean { if (!numMap.containsKey(val)) { return false } val idx numMap[val]!! val last nums[nums.size - 1] nums[idx] last numMap[last] idx nums.removeAt(nums.size - 1) numMap.remove(val) return true } fun getRandom(): Int { return nums[(0 until nums.size).random()] } }class RandomizedSet { private var numMap: [Int: Int] private var nums: [Int] init() { numMap [:] nums [] } func insert(_ val: Int) - Bool { if numMap[val] ! nil { return false } numMap[val] nums.count nums.append(val) return true } func remove(_ val: Int) - Bool { guard let idx numMap[val] else { return false } let last nums[nums.count - 1] nums[idx] last numMap[last] idx nums.removeLast() numMap.removeValue(forKey: val) return true } func getRandom() - Int { return nums[Int.random(in: 0..nums.count)] } }use rand::Rng; struct RandomizedSet { num_map: HashMapi32, usize, nums: Veci32, } impl RandomizedSet { fn new() - Self { RandomizedSet { num_map: HashMap::new(), nums: Vec::new(), } } fn insert(mut self, val: i32) - bool { if self.num_map.contains_key(val) { return false; } self.num_map.insert(val, self.nums.len()); self.nums.push(val); true } fn remove(mut self, val: i32) - bool { if let Some(idx) self.num_map.get(val) { let last *self.nums.last().unwrap(); self.nums[idx] last; self.num_map.insert(last, idx); self.nums.pop(); self.num_map.remove(val); true } else { false } } fn get_random(self) - i32 { let idx rand::thread_rng().gen_range(0..self.nums.len()); self.nums[idx] } }复杂度分析时间复杂度三个操作均为 O(1)平均。空间复杂度O(n)。仓库源码对照三种语言的实现细节仓库中的提交版源码与题解文档思路一致但变量命名和写法各有特色值得对照阅读python/0380-insert-delete-getrandom-o1.py字段命名为self.dict与self.list。remove中通过元组赋值self.list[idx], self.dict[last_element] last_element, idx一步完成数组覆盖 map 下标更新语义清晰getRandom用choice(self.list)实现随机取值。java/0380-insert-delete-getrandom-o1.java字段命名为indexingHashMap与numbersArrayList。remove中显式先numbers.set(indexElement, lastElement)覆盖数组再更新indexing中的下标先 put 再 remove最后numbers.remove(lastIndex)弹出末尾顺序与题解文档强调的先更新 map、再删除完全一致。cpp/0380-insert-delete-getrandom-o1.cpp字段命名为indicesunordered_map与valuesvector。插入时用indices[val] values.size() - 1记录下标删除时先用indices[values[values.size()-1]] idx更新末元素下标再覆盖数组、pop_back、erase。typescript/0380-insert-delete-getrandom-o1.ts用普通对象map: { [key: number]: number }充当哈希表hasOwnProperty判重arr.at(-1)取末元素。rust/0380-insert-delete-getrandom-o1.rs直接调用Vec::swap_remove(idx)一步完成交换 弹出再用entry(...).and_modify(...)更新被换到前面的末元素下标体现了 Rust 标准库对这一模式的原生支持。这些实现共同印证了题解文档的核心结论只要保证先更新被交换元素在 map 中的下标再从数组尾部弹出并删除 map 键swap-and-pop 就能在任意语言中安全地以 O(1) 完成删除。常见陷阱与易错点陷阱一忘记更新被交换元素的下标删除过程中把待删元素与最后一个元素交换后必须先用numMap[last] idx更新末元素在哈希表中的下标再执行删除。如果漏掉这一步被换到idx位置的last在 map 中仍然记录着旧下标后续对last的任何操作再次删除、再次插入等都会读到过期数据导致行为错误。例如nums [10, 20, 30, 40]删除20idx 1last 40正确做法是把40覆盖到下标 1并把 map 中40的下标从 3 改为 1最后弹出末尾、删除20的键。若跳过更新 40 的下标则 map 中40 → 3而数组中40实际在位置 1下一次remove(40)会访问错误位置。陷阱二删除最后一个元素的边界情况当待删除元素恰好位于数组末尾idx len(nums) - 1时交换操作相当于和自己交换行为上是无害的。但要注意操作顺序必须先更新 map把last的下标写成idx此时last就是val自身等于把它的下标原地覆盖再分别从数组和 map 中删除。若反过来先从 map 删除再更新就会在更新时写入一个已被删除的键或者因数组已弹出而取错末元素。陷阱三只用哈希表而不用数组常见的第一版实现是只用一个哈希表insert/remove 都是 O(1)但getRandom()需要把 keys 转成列表或遍历到随机位置退化为 O(n)。每次调用getRandom()都重新转换 keys 的做法直接违背了 O(1) 的要求。哈希表 数组的组合缺一不可数组提供 O(1) 随机访问哈希表为 swap-and-pop 删除提供 O(1) 的下标查找。总结纯哈希表方案实现最简单但getRandom()为 O(n)无法满足题目约束。哈希表 动态数组方案利用 swap-and-pop 技巧使 insert、remove、getRandom 三项操作全部达到 O(1) 平均复杂度空间 O(n)是本题的标准最优解。实现删除时牢记两个铁律先更新被交换元素的 map 下标再执行任何删除注意待删元素就在末尾时的自交换边界情况。这一索引表 有序容器 交换删除的组合模式是高频设计范式值得在面试与工程中反复练习。仓库内完整多语言实现可对照 题解文档 与 python 实现、java 实现、cpp 实现 进行复习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考