实现一个随机点名系统

题目描述
设计一个数据结构，能够支持以下操作：

1. insert(name)：将一个新名字插入到系统中。
2. delete(name)：从系统中删除一个名字。
3. getRandom()：以等概率随机返回系统中当前存在的任意一个名字。
   要求所有操作的时间复杂度在平均情况下为 O(1)。

解题过程循序渐进讲解

这个问题的核心在于，我们通常接触的数组、链表、哈希表等数据结构无法同时满足 O(1) 时间的插入、删除和随机访问。下面我们一步步分析，并构建出最终的解决方案。

步骤1：分析数据结构的能力限制

• 数组（或动态数组）：通过索引进行随机访问是 O(1)。但是，在知道索引的情况下，删除一个元素（除非是最后一个）通常需要移动后续元素，是 O(n)。在不知道索引时，查找元素本身也是 O(n)。
• 哈希表（字典/集合）：插入和删除是 O(1)。然而，它无法支持等概率的随机访问，因为哈希表内部元素存储位置是由哈希函数决定的，不是连续有序的，无法直接生成一个有效的随机索引。
• 链表：删除指定节点（如果有其引用）是 O(1)，但查找节点是 O(n)，且无法随机访问。

结论：单一数据结构无法满足所有要求，需要组合使用。

步骤2：组合数据结构的核心思路
我们结合 数组 和 哈希表 的优势：

1. 数组 list：用来按插入顺序存储所有的名字。这样，我们可以通过一个在 [0, 数组长度-1] 范围内生成的随机整数索引，在 O(1) 时间内获取一个随机名字。
2. 哈希表 dict：用来建立 名字 (name) -> 该名字在数组中的索引 (index) 的映射。这样，当我们知道一个名字时，可以在 O(1) 时间内找到它在数组中的位置。

步骤3：关键挑战——实现 O(1) 删除
在只有数组的情况下，删除中间一个元素（比如索引 i 处的元素）会导致后续所有元素前移，破坏 O(1) 的保证。
我们的解决方案是：

1. 通过哈希表 dict[name] 快速找到待删除名字 name 在数组中的索引 i。
2. 为了不移动元素，我们将数组 最后一个元素 last_name 复制到当前要删除的位置 i 上，覆盖掉待删除的名字。
3. 更新哈希表中 last_name 对应的索引为 i（因为它的位置变了）。
4. 在数组中删除最后一个元素（操作是 O(1)）。
5. 在哈希表中删除键为 name 的条目。

这个过程的关键在于，删除后数组的其他元素索引保持不变，只有被移动的最后一个元素的索引需要更新。 这就保证了删除操作的 O(1) 复杂度。

步骤4：详细操作流程与示例

假设初始状态：

• list = ["Alice", "Bob", "Charlie", "David"]
• dict = {"Alice":0, "Bob":1, "Charlie":2, "David":3}

操作1：getRandom()
生成一个随机索引，例如 randint(0, 3) 得到 2，返回 list[2]，即 "Charlie"。

操作2：delete("Bob")

1. 通过 dict["Bob"] 找到索引 i = 1。
2. 将数组最后一个元素 "David"（索引3）复制到索引1的位置。现在 list = ["Alice", "David", "Charlie", "David"]。
3. 更新 dict["David"] 的值为新的索引 1。dict = {"Alice":0, "David":1, "Charlie":2, "David":3}。
4. 删除数组的最后一个元素：list.pop()。现在 list = ["Alice", "David", "Charlie"]。
5. 从哈希表中删除键 "Bob"：dict.pop("Bob")。最终 dict = {"Alice":0, "David":1, "Charlie":2}。

操作3：insert("Eve")

1. 将 "Eve" 追加到数组末尾：list.append("Eve")，假设新索引为 3（当前数组长度为3，追加后索引为3）。现在 list = ["Alice", "David", "Charlie", "Eve"]。
2. 在哈希表中添加映射：dict["Eve"] = 3。现在 dict = {"Alice":0, "David":1, "Charlie":2, "Eve":3}。

步骤5：边界情况与代码框架（Python示例）

import random

class RandomNameSystem:
    def __init__(self):
        # 存储名字的列表
        self.names = []
        # 名字 -> 索引 的映射字典
        self.name_to_index = {}

    def insert(self, name: str) -> None:
        """
        插入一个名字。
        如果名字已存在，可以根据需求决定是否处理（这里假设允许重复，但需注意随机概率）。
        为简化，我们先假设名字唯一。如果名字已存在，则更新其位置的意义不大，通常选择跳过或报错。
        这里实现为：如果名字已存在，则不做任何操作。
        """
        if name in self.name_to_index:
            return # 或可以选择抛出异常
        # 将名字追加到列表末尾
        self.names.append(name)
        # 记录名字对应的最新索引
        self.name_to_index[name] = len(self.names) - 1

    def delete(self, name: str) -> bool:
        """
        删除一个名字。
        返回是否成功删除。
        """
        if name not in self.name_to_index:
            return False
        
        # 找到待删除名字的索引
        idx_to_remove = self.name_to_index[name]
        # 获取列表最后一个名字
        last_name = self.names[-1]
        
        # 用最后一个名字覆盖要删除的位置
        self.names[idx_to_remove] = last_name
        # 更新哈希表中最后一个名字的索引
        self.name_to_index[last_name] = idx_to_remove
        
        # 删除列表最后一个元素（现在是冗余的）
        self.names.pop()
        # 从哈希表中删除目标名字
        del self.name_to_index[name]
        
        return True

    def getRandom(self) -> str:
        """
        随机返回一个名字。
        假设调用时系统非空。
        """
        # 从 [0, len(names)-1] 中随机选择一个索引
        random_index = random.randint(0, len(self.names) - 1)
        return self.names[random_index]

步骤6：复杂度分析与总结

• 时间复杂度：
  • insert(name)：列表末尾追加和哈希表插入都是 O(1)。
  • delete(name)：通过哈希表找索引 O(1)，列表末尾元素访问和赋值 O(1)，列表 pop() 最后一个元素 O(1)，哈希表删除 O(1)。整体 O(1)。
  • getRandom()：生成随机整数 O(1)，列表按索引访问 O(1)。
• 空间复杂度：O(N)，用于存储 N 个名字及其索引映射。

核心思想：这种结合 动态数组（支持快速随机访问） 和 哈希表（支持快速查找定位） 的设计模式，通过用最后一个元素覆盖待删除元素并更新索引的技巧，完美实现了 O(1) 时间复杂度的插入、删除和随机访问，是解决此类问题的经典方法。这个结构有时也被称为“随机化集合”。