设计支持快速插入、删除和随机访问的数据结构

题目

设计支持快速插入、删除和随机访问的数据结构

信息

• 类型：问答
• 难度：⭐⭐

考点

哈希表, 数组, 数据结构设计, 时间复杂度分析

快速回答

设计一个支持以下操作的数据结构：

• insert(val)：插入元素（若不存在）
• remove(val)：删除元素（若存在）
• getRandom()：随机返回一个元素（概率均等）

所有操作平均时间复杂度应为 O(1)。解决方案：

1. 使用动态数组存储元素，支持 O(1) 随机访问
2. 使用哈希表记录元素到数组索引的映射
3. 插入时：数组末尾添加，哈希表记录索引
4. 删除时：将待删元素与末尾元素交换，更新哈希表索引，删除末尾元素
5. 随机访问：生成随机索引返回数组元素

问题分析

需要设计一个数据结构（通常称为RandomizedSet），支持O(1)时间复杂度的插入、删除和随机访问。核心挑战在于：

• 数组支持O(1)随机访问但删除中间元素需要O(n)
• 哈希表支持O(1)插入删除但不支持随机访问

解决方案

结合动态数组和哈希表的优势：

• 动态数组：存储实际元素，支持O(1)随机访问
• 哈希表：存储元素值到数组索引的映射（值 → 索引）

操作实现：

1. 插入操作：

   def insert(self, val: int) -> bool:
       if val in self.hash_map: 
           return False
       self.arr.append(val)
       self.hash_map[val] = len(self.arr) - 1
       return True

2. 删除操作（关键步骤）：

   def remove(self, val: int) -> bool:
       if val not in self.hash_map: 
           return False
   
       # 获取待删除元素的索引
       idx = self.hash_map[val]
   
       # 将最后一个元素移动到待删除位置
       last_val = self.arr[-1]
       self.arr[idx] = last_val
   
       # 更新哈希表中最后一个元素的索引
       self.hash_map[last_val] = idx
   
       # 删除数组末尾元素和哈希表记录
       self.arr.pop()
       del self.hash_map[val]
       return True

3. 随机访问：

   def getRandom(self) -> int:
       return random.choice(self.arr)

时间复杂度分析

常见错误

• 直接删除数组中间元素：导致O(n)元素移动
• 忘记更新哈希表：删除后未更新被移动元素的索引
• 处理重复元素：题目通常要求元素唯一（需先检查存在性）

最佳实践

• 在删除操作中先更新再删除，避免索引失效
• 使用语言内置的随机函数（如Python的random.choice）
• 边界检查：空数据结构时getRandom应返回错误

扩展知识

• 支持重复元素：哈希表改为存储{元素: 索引集合}，但getRandom复杂度不变
• 实际应用场景：负载均衡随机路由、抽奖系统、随机算法
• 变种问题：设计支持O(1)查找最小/最大元素的结构（可结合堆）