哈希算法题目：设计一个基于哈希的在线选举系统

题目描述
设计一个在线选举系统，能够记录候选人在不同时间点的得票数，并支持快速查询在任意时间点得票最多的候选人。系统需要实现以下功能：

• vote(candidate, timestamp)：在给定时间戳为候选人投票
• query(timestamp)：查询在给定时间戳时得票最多的候选人（如果平票，返回最近获得当前票数的候选人）

解题过程

1. 问题分析

• 投票按时间顺序发生，时间戳严格递增
• 需要记录每个候选人的累计得票数随时间的变化
• 查询时需要知道在特定时间点的领先候选人
• 关键难点：如何高效处理时间点查询（不能重新计算所有历史投票）

2. 数据结构设计

class OnlineElectionSystem:
    def __init__(self):
        # 记录每个候选人的总票数
        self.votes = {}
        # 记录每个时间点的领先候选人
        self.leading_at_time = {}
        # 记录当前最大票数
        self.current_max_votes = 0
        # 记录当前领先候选人
        self.current_leader = None
        # 记录所有时间戳（按顺序）
        self.timestamps = []

3. 投票处理算法

def vote(self, candidate: str, timestamp: int) -> None:
    # 更新候选人的票数
    self.votes[candidate] = self.votes.get(candidate, 0) + 1
    
    # 检查是否需要更新领先者
    if self.votes[candidate] > self.current_max_votes:
        self.current_max_votes = self.votes[candidate]
        self.current_leader = candidate
    elif self.votes[candidate] == self.current_max_votes:
        # 平票情况下，选择最近获得这个票数的候选人
        self.current_leader = candidate
    
    # 记录这个时间点的领先者
    self.leading_at_time[timestamp] = self.current_leader
    self.timestamps.append(timestamp)

4. 查询算法设计

def query(self, timestamp: int) -> str:
    # 使用二分查找找到小于等于给定时间戳的最大时间戳
    left, right = 0, len(self.timestamps) - 1
    result_index = -1
    
    while left <= right:
        mid = (left + right) // 2
        if self.timestamps[mid] <= timestamp:
            result_index = mid
            left = mid + 1
        else:
            right = mid - 1
    
    if result_index == -1:
        return ""  # 没有在给定时间之前的投票记录
    
    # 返回对应时间点的领先者
    target_time = self.timestamps[result_index]
    return self.leading_at_time[target_time]

5. 完整实现和优化

class OnlineElectionSystem:
    def __init__(self):
        self.votes = {}
        self.leading_at_time = {}
        self.current_max_votes = 0
        self.current_leader = None
        self.timestamps = []
    
    def vote(self, candidate: str, timestamp: int) -> None:
        # 更新票数
        self.votes[candidate] = self.votes.get(candidate, 0) + 1
        
        # 判断是否需要更新领先者
        current_votes = self.votes[candidate]
        
        if current_votes >= self.current_max_votes:
            # 票数更多或者平票但最近获得
            if current_votes > self.current_max_votes:
                self.current_max_votes = current_votes
            self.current_leader = candidate
        
        # 记录时间点和对应的领先者
        self.leading_at_time[timestamp] = self.current_leader
        self.timestamps.append(timestamp)
    
    def query(self, timestamp: int) -> str:
        if not self.timestamps or timestamp < self.timestamps[0]:
            return ""
        
        # 二分查找实现
        left, right = 0, len(self.timestamps) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if self.timestamps[mid] <= timestamp:
                left = mid + 1
            else:
                right = mid - 1
        
        # right指向小于等于timestamp的最大索引
        if right < 0:
            return ""
        
        return self.leading_at_time[self.timestamps[right]]

6. 算法复杂度分析

• 时间复杂度：
  • vote操作：O(1)，哈希表操作和列表追加都是常数时间
  • query操作：O(log n)，二分查找时间戳列表
• 空间复杂度：O(n)，存储所有时间点的投票记录

7. 测试用例验证

# 测试示例
system = OnlineElectionSystem()
system.vote("Alice", 1)
system.vote("Bob", 2)
system.vote("Alice", 3)
system.vote("Charlie", 4)
system.vote("Bob", 5)

print(system.query(1))  # 输出: Alice
print(system.query(3))  # 输出: Alice  
print(system.query(4))  # 输出: Alice (平票，但Alice最近获得这个票数)
print(system.query(5))  # 输出: Bob

这个解决方案通过维护时间点与领先者的映射，结合二分查找，实现了高效的在线选举查询功能。