基于哈希表的随机集合（常数时间插入、删除和获取随机元素） 题目描述 设计一个集合数据结构，支持在平均 O(1) 时间复杂度内执行以下操作： insert(val) ：向集合中插入一个元素 val 。如果元素已存在，返回 false ；否则插入并返回 true 。 remove(val) ：从集合中移除元素 val 。如果元素存在，移除并返回 true ；否则返回 false 。 getRandom() ：随机返回集合中的一个元素。集合中的每个元素被返回的概率应 完全相同 。 注意：你可以假设所有插入的元素都是 唯一 的（即没有重复值），并且 remove 操作总是针对集合中存在的有效元素进行测试。 解题过程 核心难点分析 哈希表（如 unordered_map 或 dict ）可以在 O(1) 时间内完成插入、删除和查询，但无法在 O(1) 时间内随机返回一个元素（因为哈希表内部元素无序，不支持按索引访问）。 数组（或动态列表）支持 O(1) 时间的随机访问（通过下标），但查找和删除特定元素需要 O(n) 时间（需要遍历查找）。 因此，需要结合两者的优势：用哈希表存储元素值到数组索引的映射，用数组存储实际元素值。 数据结构设计 一个动态数组 vec ，按顺序存储集合中的元素。 一个哈希表 index_map ，键为元素值，值为该元素在数组 vec 中的下标。 操作实现细节 步骤 1：insert(val) 操作 先检查哈希表：如果 val 已存在于 index_map 中，直接返回 false 。 如果不存在： 将 val 追加到数组 vec 的末尾。 在哈希表 index_map 中记录 val 对应的索引（即 vec 的最后一个位置）。 返回 true 。 时间复杂度 ：O(1) 平均（数组末尾插入 O(1)，哈希表插入 O(1)）。 步骤 2：remove(val) 操作 先检查哈希表：如果 val 不存在于 index_map 中，返回 false 。 如果存在： 获取 val 在数组中的索引 idx 。 为了在 O(1) 时间内删除数组中的元素（避免整体移动），采用“交换后删除”策略： 找到数组最后一个元素 last_val 。 将 last_val 移动到索引 idx 的位置（即 vec[idx] = last_val ）。 更新哈希表中 last_val 对应的索引为 idx 。 删除数组的最后一个元素（ vec.pop_back() ）。 从哈希表中删除键 val 。 返回 true 。 关键点 ：通过交换，我们总是删除数组的最后一个元素，从而保持数组的连续性，且更新哈希表映射只需 O(1) 时间。 时间复杂度 ：O(1) 平均。 步骤 3：getRandom() 操作 在 [0, vec.size() - 1] 范围内生成一个随机整数 rand_idx 。 返回 vec[rand_idx] 。 时间复杂度 ：O(1)。 举例说明 假设依次执行以下操作： insert(10) → 数组 [10] ，哈希表 {10:0} ，返回 true 。 insert(20) → 数组 [10, 20] ，哈希表 {10:0, 20:1} ，返回 true 。 insert(30) → 数组 [10, 20, 30] ，哈希表 {10:0, 20:1, 30:2} ，返回 true 。 getRandom() → 随机返回 10、20 或 30 中的一个，每个概率 1/3。 remove(20) ： 获取 idx = 1 （20 的索引）。 将最后一个元素 30 移动到 idx = 1 处，数组变为 [10, 30] 。 更新哈希表中 30 的索引为 1（即 {10:0, 30:1} ）。 删除数组最后一个位置（已移动，实际上数组现在只有两个元素）。 删除哈希表中键 20。 返回 true 。 getRandom() → 随机返回 10 或 30，每个概率 1/2。 边界情况与注意事项 删除最后一个元素时：如果删除的元素本来就是数组最后一个，则直接删除，无需交换和更新其他映射。 随机数生成：确保随机索引在数组当前有效范围内。 并发安全：本设计未考虑多线程并发，实际应用中需加锁或使用并发数据结构。 总结 通过结合哈希表（快速查找）和动态数组（支持随机访问），我们可以在 O(1) 平均时间内完成插入、删除和获取随机元素的操作。关键在于删除时通过交换元素位置来避免数组大规模移动，并同步更新哈希表的索引映射。这种数据结构在需要快速随机抽样的场景中非常有用，例如随机化算法、游戏机制或负载均衡中的随机选择。