基于哈希表的随机集合（常数时间插入、删除和获取随机元素） 题目描述：设计一个数据结构，支持在平均 O(1) 时间内完成以下操作： insert(val) ：向集合中插入一个元素，如果元素已存在则返回 false，否则插入并返回 true。 remove(val) ：从集合中移除一个元素，如果元素不存在则返回 false，否则移除并返回 true。 getRandom() ：随机返回集合中的一个元素，每个元素被返回的概率应相等。 注意：你可以假设所有插入的元素是数字（题目通常适用于任意可哈希类型）。 解题过程循序渐进讲解： 问题分析 如果只需要插入和删除，使用哈希集合（如 Python 的 set）即可实现 O(1) 操作。但 getRandom() 要求随机返回一个元素，且概率相等。哈希集合本身不支持按索引随机访问，若将其转换为列表再随机选择，每次 getRandom() 需要 O(n) 时间，不符合要求。因此，我们需要结合哈希表和数组（或动态数组）的特性。 核心思路 使用一个数组 list 存储元素，保证每个元素在数组中的位置是连续的（从 0 开始）。再使用一个哈希表 dict ，键为元素值，值为该元素在数组中的索引。这样： 插入时，将元素追加到数组末尾，并在哈希表中记录索引，均为 O(1)。 删除时，通过哈希表获得元素索引，将该索引位置的元素替换为数组末尾元素，然后删除数组末尾，并更新哈希表中被移动元素的索引，最后删除哈希表中目标元素的记录，平均 O(1)。 随机访问时，生成一个随机索引，从数组中返回对应元素，O(1)。 详细步骤 a. 数据结构初始化 创建空数组 self.nums 和空字典 self.idx_map 。 b. insert 操作 检查 val 是否已在 self.idx_map 中： 如果存在，返回 false 。 如果不存在： 将 val 追加到 self.nums 末尾。 在 self.idx_map[val] 中记录索引（ len(self.nums) - 1 ）。 返回 true 。 c. remove 操作 检查 val 是否在 self.idx_map 中： 如果不存在，返回 false 。 如果存在： 获取 val 的索引 i 。 获取数组最后一个元素 last = self.nums[-1] 。 将 self.nums[i] 赋值为 last （即将末尾元素移动到被删除元素的位置）。 在 self.idx_map[last] 中更新索引为 i （因为 last 被移动了）。 删除 self.nums 的最后一个元素（弹出末尾，O(1)）。 删除 self.idx_map[val] 。 返回 true 。 d. getRandom 操作 从 self.nums 中随机选择一个索引，返回该位置元素。使用 random.randint(0, len(self.nums)-1) 或 random.choice 实现。 关键点说明 删除操作中，将末尾元素移动到被删除位置，是为了保持数组的连续性，避免出现“空洞”，从而保证 getRandom 的均匀性。 更新哈希表时，需先更新被移动元素（ last ）的索引，再删除目标元素（ val ）的记录，顺序不能颠倒，尤其当被删除元素就是最后一个元素时（ val == last ），也能正确处理。 所有操作平均时间复杂度为 O(1)，满足题目要求。 示例演示 插入 1, 2, 3 后： nums = [1, 2, 3] , idx_map = {1:0, 2:1, 3:2} 。 删除 2： i = 1 , last = 3 。 将 nums[1] 设为 3，数组变为 [1, 3, 3] 。 更新 idx_map[3] = 1 。 弹出末尾， nums = [1, 3] 。 删除 idx_map[2] ，得到 {1:0, 3:1} 。 此时 getRandom 返回 1 或 3 的概率各为 1/2。 通过这种结合数组和哈希表的设计，我们完美地实现了所有操作的平均 O(1) 时间复杂度。