随机点名系统

这是一个基于哈希算法的随机点名系统设计题目。我们将设计一个能够支持添加学生、删除学生、随机点名（确保公平随机，且不会重复点到同一名学生直到所有学生都被点过）的功能。

题目描述

设计一个支持以下操作的随机点名系统：

1. add(name): 添加一名学生到系统中。
2. remove(name): 从系统中移除一名学生。
3. random(): 随机返回系统中当前存在的一名学生的名字，并且：
   • 在同一轮中，确保不会重复点到同一名学生。
   • 当所有学生都被点过一次后，开始新的一轮，重新允许点已经点过的学生。

解题过程

我们将循序渐进地讲解如何利用哈希表（字典）和列表（动态数组）来实现这个系统。

步骤1：理解需求与核心挑战

• 我们需要存储所有学生的名字，并能快速进行添加和删除操作。
• 随机点名需要等概率地选择一名学生。
• 关键点在于同一轮不重复，即每次随机选择后，需要记录哪些学生已经被点过名，直到所有学生都被点过一次才重置。
• 学生数量会动态变化（添加/删除），因此重置条件需要灵活处理。

步骤2：选择数据结构

为了高效地支持这些操作，我们选择以下两个核心数据结构：

• 列表 students: 按添加顺序存储所有学生的名字。列表支持通过索引快速访问，便于实现等概率随机选择。
• 哈希表 name_to_index: 键是学生名字，值是该名字在 students 列表中的索引。这使得我们可以通过名字快速定位到列表中的位置，从而实现 O(1) 的删除操作（通过交换技巧）。
• 集合 picked_in_round: 存储本轮已经点过的学生名字，用于确保同一轮不重复。
• 整数 remaining_in_round: 记录本轮还未被点过的学生数量。当这个值降为0时，需要重置本轮状态。

步骤3：详细设计每个操作

初始化

• 创建一个空列表 students。
• 创建一个空字典 name_to_index。
• 创建一个空集合 picked_in_round。
• 设置 remaining_in_round = 0（因为初始时没有学生，所以本轮未点人数为0）。

添加操作 add(name)

1. 检查学生是否已经存在（通过 name_to_index）。如果存在，则不重复添加。
2. 如果不存在：
   • 将名字追加到 students 列表末尾。
   • 在 name_to_index 中记录该名字对应的索引（即 len(students)-1）。
   • 重要：新加入的学生应该被视为本轮还未被点过。因此：
     • 将其名字加入 picked_in_round？不对，picked_in_round 存储的是已点过的。所以新学生不需要加入 picked_in_round。
     • 但是，remaining_in_round 需要增加1，因为新学生加入了本轮候选池。
   • 如果 remaining_in_round 原本为0（表示上一轮刚结束），现在新加入学生后，本轮就开始了，remaining_in_round 变为1。

删除操作 remove(name)

1. 检查学生是否存在。如果不存在，直接返回。
2. 如果存在：
   • 获取该学生在 students 列表中的索引 idx。
   • 为了在列表中 O(1) 地删除，我们采用交换技巧：
     • 将列表最后一个元素 last_name 移动到 idx 的位置。
     • 更新 name_to_index[last_name] = idx（因为它的位置变了）。
     • 从 students 列表中弹出最后一个元素（现在它已经被移动到前面了）。
     • 从 name_to_index 中删除 name。
   • 处理本轮状态：
     • 如果该学生在本轮已经被点过（即名字在 picked_in_round 中），则从 picked_in_round 中移除该名字。但是，remaining_in_round 不需要变化（因为已经被点过的学生不再参与本轮随机）。
     • 如果该学生在本轮还未被点过（名字不在 picked_in_round 中），则 remaining_in_round 需要减1（因为少了一个候选者）。
   • 最后，检查 remaining_in_round 是否为0，如果为0则重置本轮（清空 picked_in_round，并将 remaining_in_round 设置为当前学生总数）。

随机点名操作 random()

1. 如果当前没有学生（len(students) == 0），返回空或抛出异常。
2. 如果 remaining_in_round == 0，表示本轮所有学生都已被点过，需要重置本轮：
   • 清空 picked_in_round 集合。
   • 设置 remaining_in_round = len(students)。
3. 现在，我们需要从未被点过的学生中随机选择一个：
   • 生成一个随机索引 rand_idx，范围在 [0, remaining_in_round-1]？不对，我们不能直接这样，因为未被点过的学生在列表中不是连续存储的。
   • 正确做法：我们采用“从所有学生中随机选择，如果选到已点过的则重试”的方法。但重试在极端情况下（比如只剩一个未点）可能多次失败，效率低。
   • 优化做法：我们可以维护一个“未点学生索引列表”或者使用“交换到列表末尾”的技巧。这里采用一种简单且高效的方法：
     • 维护一个列表 candidates 存储所有学生的索引，但每次随机选择后，将选中的索引与列表末尾的索引交换，然后缩小候选范围。但我们还需要处理动态添加/删除，实现较复杂。
   • 更清晰的实现：
     • 我们使用 students 列表，但随机选择时，如果选到已点过的学生，就重新随机，直到选到未点过的。由于 remaining_in_round 较大时，重试次数期望是常数，可以接受。
4. 具体步骤：
   • 循环直到找到未点过的学生：
     • 随机生成一个索引 rand_idx ∈ [0, len(students)-1]。
     • 对应的名字 chosen = students[rand_idx]。
     • 如果 chosen 不在 picked_in_round 中，则找到。
   • 将 chosen 加入 picked_in_round。
   • remaining_in_round 减1。
   • 返回 chosen。

步骤4：算法复杂度分析

• 添加 add(name): O(1) 平均（哈希表插入 + 列表追加）。
• 删除 remove(name): O(1) 平均（哈希表查找 + 列表交换弹出 + 集合删除）。
• 随机点名 random(): 期望 O(1)。因为随机选择后检查是否已点过是 O(1)（集合查找），而重试次数的期望是 n / remaining_in_round，当 remaining_in_round 较小时，重试次数增加，但最坏情况（如只剩一个未点）期望重试次数为 n，可以通过优化避免（但这里我们接受这种简单实现）。

步骤5：伪代码实现

import random

class RandomRollCall:
    def __init__(self):
        self.students = []          # 列表存储名字
        self.name_to_index = {}     # 名字 -> 索引
        self.picked_in_round = set() # 本轮已点名字集合
        self.remaining_in_round = 0  # 本轮剩余未点人数

    def add(self, name):
        if name in self.name_to_index:
            return
        self.students.append(name)
        self.name_to_index[name] = len(self.students) - 1
        self.remaining_in_round += 1

    def remove(self, name):
        if name not in self.name_to_index:
            return
        idx = self.name_to_index[name]
        last_name = self.students[-1]
        # 将最后一个元素移到要删除的位置
        self.students[idx] = last_name
        self.name_to_index[last_name] = idx
        # 删除最后一个元素
        self.students.pop()
        del self.name_to_index[name]
        # 更新本轮状态
        if name in self.picked_in_round:
            self.picked_in_round.remove(name)
        else:
            self.remaining_in_round -= 1
        # 如果本轮剩余为0，重置
        if self.remaining_in_round == 0:
            self.picked_in_round.clear()
            self.remaining_in_round = len(self.students)

    def random(self):
        if not self.students:
            return None
        if self.remaining_in_round == 0:
            self.picked_in_round.clear()
            self.remaining_in_round = len(self.students)
        while True:
            rand_idx = random.randint(0, len(self.students) - 1)
            chosen = self.students[rand_idx]
            if chosen not in self.picked_in_round:
                self.picked_in_round.add(chosen)
                self.remaining_in_round -= 1
                return chosen

步骤6：示例演示

假设系统初始为空，依次执行：

1. add("Alice"), add("Bob"), add("Charlie")
   • students = ["Alice", "Bob", "Charlie"], remaining_in_round = 3
2. random() → 假设返回 "Bob"
   • picked_in_round = {"Bob"}, remaining_in_round = 2
3. random() → 假设返回 "Alice"
   • picked_in_round = {"Bob", "Alice"}, remaining_in_round = 1
4. remove("Charlie")
   • students = ["Alice", "Bob"], remaining_in_round = 0（因为Charlie是唯一未点的，删除后本轮无人可点）
   • 自动重置：picked_in_round = {}, remaining_in_round = 2
5. random() → 可能返回 "Alice" 或 "Bob"（新的一轮开始）。

总结

这个随机点名系统通过哈希表实现快速的名字查找和索引更新，通过列表存储学生顺序以支持随机访问，通过集合记录已点名学生保证同一轮不重复。整个设计在平均情况下实现了 O(1) 时间复杂度的添加、删除和随机点名操作，满足公平性和动态性要求。