哈希算法题目：随机点名系统

题目描述

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

1. 初始化：给定一组学生名单（可能有重复名字）。
2. 添加：将一个新学生加入名单。
3. 删除：从名单中移除一个学生（如果存在多个同名，只删除一个）。
4. 随机点名：以等概率随机返回名单中的一个学生，并确保被点到的人在下一次被点到的概率暂时降低（可选扩展）。

示例：

操作：
初始化：["Alice", "Bob", "Charlie", "Bob"]
随机点名 → 可能返回 "Alice"、"Bob" 或 "Charlie"（注意有两个"Bob"，概率会更高）
添加 "David"
删除 "Bob" → 移除一个"Bob"，名单中剩下一个"Bob"
随机点名 → 等概率返回 "Alice"、"Bob"、"Charlie"、"David"

解题过程

第一步：分析核心需求

1. 需要快速插入、删除（平均 O(1)）。
2. 需要等概率随机访问（即通过随机索引直接获取元素，O(1)）。
3. 要处理重复名字（每个名字独立计数）。
4. 扩展需求：点名后降低其下次概率，可通过调整权重实现，但需注意复杂度。

第二步：选择数据结构

• 数组：支持 O(1) 的随机访问（通过随机下标），但删除中间元素是 O(n)，除非与末尾交换。
• 哈希表：实现名字到索引的映射，方便 O(1) 查找和删除（通过交换到末尾再删除）。
• 因此，采用 数组 + 哈希表 的组合：
  • 数组 list 存储所有学生。
  • 哈希表 map 存储每个学生名在数组中的索引列表（因为可能有重复）。但为了简化删除操作，可以用名字到索引的映射，但若有重复，一个名字对应多个索引，删除时需选一个索引处理。

第三步：详细设计（基础版，不含概率调整）

1. 初始化：

   • 数组 list 直接存储输入名单。
   • 哈希表 map 的键是名字，值是一个列表，存储这个名字在 list 中的所有索引。

2. 添加学生 add(name)：

   • 将 name 追加到 list 末尾。
   • 在 map[name] 的索引列表中加入这个新索引。

3. 删除学生 remove(name)：

   • 从 map[name] 中取出一个索引（如最后一个）idx。
   • 将 list[idx] 与 list 的最后一个元素交换。
   • 更新哈希表：原本在末尾的元素，其索引列表需要更新（原来指向 last 的位置改为 idx）。
   • 从 list 中弹出最后一个元素（即要删除的元素）。
   • 从 map[name] 的索引列表中移除 idx。如果列表为空，则从 map 中删除这个键。

4. 随机点名 randomPick()：

   • 在 [0, list.size-1] 中生成一个随机整数 r。
   • 返回 list[r]。

第四步：举例说明

假设初始名单：["Alice", "Bob", "Charlie", "Bob"]

1. 初始化后：

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

2. 添加 "David"：

   • list 变为 ["Alice", "Bob", "Charlie", "Bob", "David"]
   • map["David"] = [4]

3. 删除 "Bob"（移除一个）：

   • 从 map["Bob"] 取一个索引，如 1。
   • 将 list[1] 与 list[4]（末尾）交换 → list 变为 ["Alice", "David", "Charlie", "Bob", "Bob"]
   • 更新 map["David"] 的索引：原来的 [4] 改为 [1]。
   • 弹出末尾 → list = ["Alice", "David", "Charlie", "Bob"]
   • 从 map["Bob"] 移除索引 1，剩下 [3]。

4. 随机点名：

   • 随机选 0~3 的索引，等概率返回对应名字。

第五步：扩展功能（点名后降低下次概率）

一种简单方法：

• 每个学生有一个“权重”，初始为 1。
• 被点到后，将其权重减半（但不能为 0，比如设最小权重 0.1）。
• 随机点名时，按权重比例选择学生。

实现：

• 用别名采样（Alias Method） 或加权随机选择（如按权重数组累加，二分查找）。
• 但每次调整权重后需重新构建采样结构，O(n) 时间。
• 若对实时性要求不高，可在多次点名后批量更新。

简化版：每次点名后，将该学生放入“冷却列表”，下次点名时先从非冷却列表中选，若无则重置冷却。

第六步：复杂度分析

• 初始化：O(n)
• 添加：O(1)
• 删除：O(1) 平均（哈希表操作 + 交换）
• 随机点名：O(1)
• 扩展（权重调整）：加权随机选择 O(n) 或 O(log n) 取决于实现。

第七步：核心代码框架（基础版，无概率调整）

import random

class RandomNameSystem:
    def __init__(self, names):
        self.list = []
        self.map = {}  # name -> list of indices
        for name in names:
            self.add(name)
    
    def add(self, name):
        self.list.append(name)
        idx = len(self.list) - 1
        if name not in self.map:
            self.map[name] = []
        self.map[name].append(idx)
    
    def remove(self, name):
        if name not in self.map or not self.map[name]:
            return False
        # 取出一个索引
        idx = self.map[name].pop()
        if not self.map[name]:
            del self.map[name]
        # 与末尾交换
        last_idx = len(self.list) - 1
        if idx != last_idx:
            last_name = self.list[last_idx]
            self.list[idx] = last_name
            # 更新原来末尾元素的索引
            last_indices = self.map[last_name]
            # 找到 last_idx 在列表中的位置，改为 idx
            for i, pos in enumerate(last_indices):
                if pos == last_idx:
                    last_indices[i] = idx
                    break
        # 删除末尾
        self.list.pop()
        return True
    
    def randomPick(self):
        if not self.list:
            return None
        r = random.randint(0, len(self.list) - 1)
        return self.list[r]

关键点总结

1. 数组+哈希表 是实现 O(1) 插入、删除、随机访问的经典结构。
2. 删除时通过交换到末尾再删除，避免数组移位。
3. 处理重复名字时，哈希表需保存索引列表，并在交换时更新索引。
4. 扩展的“概率调整”可根据实际需求选择简单冷却或加权随机，注意时间开销。

这个设计可用于课堂点名、抽奖等场景，兼顾效率与公平性（可调概率）。