随机点名系统
字数 3092 2025-12-13 18:49:48

随机点名系统

题目描述
设计一个基于哈希表和链表的随机点名系统，支持在常数时间内完成插入、删除、随机返回一个姓名，并且要求随机返回的概率与姓名的长度成正比（即姓名越长，被随机点到的概率越高）。

系统功能需求

  1. insert(name): 将姓名插入系统，如果已存在则忽略。
  2. delete(name): 从系统中删除姓名，如果不存在则忽略。
  3. getRandom() -> str: 随机返回一个姓名，每个姓名被选中的概率应与其长度成正比。

解题过程循序渐进讲解

步骤1：理解核心矛盾与设计思路

首先，我们需要理解题目的核心要求：常数时间完成插入、删除、随机返回。
同时，随机返回的概率与姓名长度成正比，这是关键难点。

思路分析：

  1. 常数时间的插入和删除通常需要哈希表（dict或set）。
  2. 常数时间的等概率随机返回，通常需要数组（通过索引随机访问）。
    但本题要求概率与长度成正比，所以不能直接等概率随机访问数组元素。
  3. 解决加权随机选择的一个经典方法是“权重累积列表” + 二分查找，但这样删除时无法做到常数时间（需要更新累积和）。

权衡与选择：
为了实现常数时间的所有操作，我们需要一种能在常数时间内根据“权重”进行抽样的方法。
这里我们采用“复制法”：将每个姓名按其长度复制多份放入一个“选举池”，然后在这个池中等概率随机选择。
例如：姓名 "Tom" 长度为3，则在池中放入3个"Tom"的引用；姓名 "Alice" 长度为5，则在池中放入5个"Alice"的引用。
这样，随机从池中选一个元素，自然就实现了“概率与长度成正比”。

步骤2：数据结构设计

我们需要以下数据结构来支持常数时间的操作：

  1. 数组（列表） pool：存储“选举池”，每个元素是姓名的引用。
  2. 哈希表 name_to_indices：键是姓名，值是该姓名在pool中所有位置（索引）的集合。
    为什么需要记录所有位置？因为删除时，我们需要快速找到这个姓名在pool中的所有副本并移除。
  3. 哈希表 name_to_length（可选）：缓存每个姓名的长度，避免重复计算。

步骤3：插入操作 insert(name) 详细实现

  1. 检查姓名是否已存在：查询 name_to_indices，如果存在，直接返回。
  2. 获取姓名长度 L = len(name)。
  3. 在pool末尾连续追加L个该姓名的引用。记录这些新索引（从len(pool)到len(pool)+L-1）。
  4. 在name_to_indices[name]中插入这L个索引。
  5. （可选）在name_to_length[name]中记录L。

时间复杂度：O(L) 因为要追加L次，但平均到每个姓名的每个字符是常数，且L一般较小。
空间复杂度：O(N * 平均长度)。

步骤4：删除操作 delete(name) 详细实现

  1. 检查姓名是否存在：查询 name_to_indices，如果不存在，直接返回。
  2. 获取该姓名在pool中的所有位置索引集合 indices_set。
  3. 为了保持pool数组的连续性（方便随机访问），我们采用“交换-删除”策略：
    • 从indices_set中任选一个索引 i_to_remove（通常选最后一个索引，方便操作）。
    • 将pool的最后一个元素 last_name 复制到位置 i_to_remove（覆盖要删除的）。
    • 更新last_name对应的索引集合：
      • 从其集合中删除原最后索引 last_index。
      • 添加新索引 i_to_remove（因为这个姓名现在移动到了前面）。
    • 从pool中弹出最后一个元素（现在是重复的或无用的，已被覆盖）。
    • 从indices_set中删除索引 i_to_remove（因为该位置已被占用）。
  4. 如果indices_set变为空，则从name_to_indices中删除该姓名的键。
  5. （可选）从name_to_length中删除记录。

关键：每次删除只移除了一个副本，但我们需要移除该姓名的所有副本。
因此，我们需要重复步骤3，直到indices_set为空（即所有副本都被移除）。
删除一个姓名的总时间复杂度是O(K)，其中K是该姓名的长度（即副本数），平均来看仍然是常数（因为K较小且与姓名长度成正比）。

步骤5：随机返回操作 getRandom() 详细实现

  1. 从pool中随机选择一个索引 random_index（使用随机数生成器，范围[0, len(pool)-1]）。
  2. 返回 pool[random_index]。

由于每个姓名被放入池中的次数等于其长度，所以长姓名有更多的“票”，被随机选中的概率自然与其长度成正比。

时间复杂度：O(1)。
空间复杂度：O(N * 平均长度)。

步骤6：举例演示

假设我们依次执行：

  1. insert("Tom")
    • 长度3，pool变为：["Tom","Tom","Tom"]
    • name_to_indices = {"Tom": {0,1,2}}
  2. insert("Alice")
    • 长度5，pool变为：["Tom","Tom","Tom","Alice","Alice","Alice","Alice","Alice"]
    • name_to_indices = {"Tom": {0,1,2}, "Alice": {3,4,5,6,7}}
  3. getRandom()
    • 随机选索引，每个索引等概率。
    • 选到0,1,2的概率是3/8，对应返回"Tom"。
    • 选到3-7的概率是5/8，对应返回"Alice"。
    • 恰好P("Tom") : P("Alice") = 3:5 = 长度比。
  4. delete("Tom")
    • 获取Tom的索引集合{0,1,2}。
    • 先删除索引2：将pool最后一个元素（索引7的"Alice"）复制到索引2，更新Alice的索引集合为{3,4,5,6,2}，弹出pool末尾，pool长度减1，Tom的集合变为{0,1}。
    • 删除索引1：将pool最后一个元素（现在是索引6的"Alice"）复制到索引1，更新Alice的索引集合为{3,4,5,2,1}，弹出末尾，Tom的集合变为{0}。
    • 删除索引0：将pool最后一个元素（索引5的"Alice"）复制到索引0，更新Alice的索引集合为{3,4,2,1,0}，弹出末尾，Tom的集合变为空，删除键"Tom"。
    • 最终pool = ["Alice","Alice","Alice","Alice","Alice"]，全部是Alice的副本。

步骤7：优化与边界情况

  1. 优化删除：
    上述删除操作需要循环L次，每次O(1)。如果姓名很长，删除可能稍慢。
    但考虑到实际场景中姓名长度有限，这是可接受的。
  2. 空池处理：
    如果pool为空，getRandom()应返回空或抛出异常。
  3. 内存优化：
    池中存储的是姓名字符串的引用，而不是副本，所以内存占用是O(N + 总字符数)。
  4. 线程安全：
    如果多线程访问，需要加锁。

总结
本题通过“按长度复制到选举池”的方法，将加权随机选择转化为等概率随机选择，从而实现了常数时间的getRandom()。
配合哈希表记录索引集合，以及“交换-删除”策略，实现了常数时间的插入和删除。
整个设计巧妙地结合了哈希表、数组和集合，满足了所有操作的时间复杂度要求。

随机点名系统 题目描述 设计一个基于哈希表和链表的随机点名系统，支持在常数时间内完成插入、删除、随机返回一个姓名，并且要求随机返回的概率与姓名的长度成正比（即姓名越长，被随机点到的概率越高）。 系统功能需求 insert(name) : 将姓名插入系统，如果已存在则忽略。 delete(name) : 从系统中删除姓名，如果不存在则忽略。 getRandom() -> str : 随机返回一个姓名，每个姓名被选中的概率应与其长度成正比。 解题过程循序渐进讲解 步骤1：理解核心矛盾与设计思路 首先，我们需要理解题目的核心要求：常数时间完成插入、删除、随机返回。 同时，随机返回的概率与姓名长度成正比，这是关键难点。 思路分析 ： 常数时间的插入和删除通常需要哈希表（ dict 或 set ）。 常数时间的等概率随机返回，通常需要数组（通过索引随机访问）。 但本题要求 概率与长度成正比 ，所以不能直接等概率随机访问数组元素。 解决加权随机选择的一个经典方法是“权重累积列表” + 二分查找，但这样删除时无法做到常数时间（需要更新累积和）。 权衡与选择 ： 为了实现常数时间的所有操作，我们需要一种能在常数时间内根据“权重”进行抽样的方法。 这里我们采用“复制法”：将每个姓名按其长度复制多份放入一个“选举池”，然后在这个池中等概率随机选择。 例如：姓名 "Tom" 长度为3，则在池中放入3个"Tom"的引用；姓名 "Alice" 长度为5，则在池中放入5个"Alice"的引用。 这样，随机从池中选一个元素，自然就实现了“概率与长度成正比”。 步骤2：数据结构设计 我们需要以下数据结构来支持常数时间的操作： 数组（列表） pool ：存储“选举池”，每个元素是姓名的引用。 哈希表 name_to_indices ：键是姓名，值是该姓名在 pool 中所有位置（索引）的集合。 为什么需要记录所有位置？因为删除时，我们需要快速找到这个姓名在 pool 中的所有副本并移除。 哈希表 name_to_length （可选）：缓存每个姓名的长度，避免重复计算。 步骤3：插入操作 insert(name) 详细实现 检查姓名是否已存在：查询 name_to_indices ，如果存在，直接返回。 获取姓名长度 L = len(name) 。 在 pool 末尾连续追加 L 个该姓名的引用。记录这些新索引（从 len(pool) 到 len(pool)+L-1 ）。 在 name_to_indices[name] 中插入这 L 个索引。 （可选）在 name_to_length[name] 中记录 L 。 时间复杂度 ：O(L) 因为要追加L次，但平均到每个姓名的每个字符是常数，且L一般较小。 空间复杂度 ：O(N * 平均长度)。 步骤4：删除操作 delete(name) 详细实现 检查姓名是否存在：查询 name_to_indices ，如果不存在，直接返回。 获取该姓名在 pool 中的所有位置索引集合 indices_set 。 为了保持 pool 数组的连续性（方便随机访问），我们采用“交换-删除”策略： 从 indices_set 中任选一个索引 i_to_remove （通常选最后一个索引，方便操作）。 将 pool 的最后一个元素 last_name 复制到位置 i_to_remove （覆盖要删除的）。 更新 last_name 对应的索引集合： 从其集合中删除原最后索引 last_index 。 添加新索引 i_to_remove （因为这个姓名现在移动到了前面）。 从 pool 中弹出最后一个元素（现在是重复的或无用的，已被覆盖）。 从 indices_set 中删除索引 i_to_remove （因为该位置已被占用）。 如果 indices_set 变为空，则从 name_to_indices 中删除该姓名的键。 （可选）从 name_to_length 中删除记录。 关键 ：每次删除只移除了一个副本，但我们需要移除该姓名的所有副本。 因此，我们需要重复步骤3，直到 indices_set 为空（即所有副本都被移除）。 删除一个姓名的总时间复杂度是O(K)，其中K是该姓名的长度（即副本数），平均来看仍然是常数（因为K较小且与姓名长度成正比）。 步骤5：随机返回操作 getRandom() 详细实现 从 pool 中随机选择一个索引 random_index （使用随机数生成器，范围 [0, len(pool)-1] ）。 返回 pool[random_index] 。 由于每个姓名被放入池中的次数等于其长度，所以长姓名有更多的“票”，被随机选中的概率自然与其长度成正比。 时间复杂度 ：O(1)。 空间复杂度 ：O(N * 平均长度)。 步骤6：举例演示 假设我们依次执行： insert("Tom") 长度3， pool 变为：[ "Tom","Tom","Tom" ] name_to_indices = {"Tom": {0,1,2}} insert("Alice") 长度5， pool 变为：[ "Tom","Tom","Tom","Alice","Alice","Alice","Alice","Alice" ] name_to_indices = {"Tom": {0,1,2}, "Alice": {3,4,5,6,7}} getRandom() 随机选索引，每个索引等概率。 选到0,1,2的概率是3/8，对应返回"Tom"。 选到3-7的概率是5/8，对应返回"Alice"。 恰好P("Tom") : P("Alice") = 3:5 = 长度比。 delete("Tom") 获取Tom的索引集合{0,1,2}。 先删除索引2：将pool最后一个元素（索引7的"Alice"）复制到索引2，更新Alice的索引集合为{3,4,5,6,2}，弹出pool末尾，pool长度减1，Tom的集合变为{0,1}。 删除索引1：将pool最后一个元素（现在是索引6的"Alice"）复制到索引1，更新Alice的索引集合为{3,4,5,2,1}，弹出末尾，Tom的集合变为{0}。 删除索引0：将pool最后一个元素（索引5的"Alice"）复制到索引0，更新Alice的索引集合为{3,4,2,1,0}，弹出末尾，Tom的集合变为空，删除键"Tom"。 最终pool = [ "Alice","Alice","Alice","Alice","Alice" ]，全部是Alice的副本。 步骤7：优化与边界情况 优化删除 ： 上述删除操作需要循环L次，每次O(1)。如果姓名很长，删除可能稍慢。 但考虑到实际场景中姓名长度有限，这是可接受的。 空池处理 ： 如果 pool 为空， getRandom() 应返回空或抛出异常。 内存优化 ： 池中存储的是姓名字符串的引用，而不是副本，所以内存占用是O(N + 总字符数)。 线程安全 ： 如果多线程访问，需要加锁。 总结 本题通过“按长度复制到选举池”的方法，将加权随机选择转化为等概率随机选择，从而实现了常数时间的 getRandom() 。 配合哈希表记录索引集合，以及“交换-删除”策略，实现了常数时间的插入和删除。 整个设计巧妙地结合了哈希表、数组和集合，满足了所有操作的时间复杂度要求。