面试题优化求解：指定时间点的得票领先候选人查询

针对你的面试题需求，要实现查询时间复杂度最优的解法，核心思路是通过预处理时间轴的全局状态快照，把每次查询的时间复杂度降到O(logM)（M为总得票数），远优于你当前的遍历筛选方案。

具体实现步骤 #

1. 预处理阶段 #

• 步骤1：统一排序所有得票记录
  把所有候选人的得票记录抽离成(时间, 候选人)的结构，然后按时间从小到大排序。如果存在同一时间的多张票，可按题目要求调整顺序（比如按候选人名称排序）。

• 步骤2：遍历生成状态快照
  初始化一个计数器Map<String, Integer> voteCount实时统计各候选人得票数，同时维护当前得票最多的候选人（处理并列情况：比如保留最早达到最高票数的候选人，或记录所有并列者，需按题目要求确定）。
  遍历排序后的得票序列，每处理完一个时间点的所有票（同时间票批量处理），就将当前时间和对应的「得票最多候选人」存入一个有序数组（或TreeMap，键为时间，值为结果）。

  举个对应示例的实例：
  假设原始数据为：

  • A: 10时、15时
  • B: 12时
  • C: 18时、19时
    排序后的序列为：(10,A), (12,B), (15,A), (18,C), (19,C)
    遍历生成的快照为：

  时间	得票最多候选人
  10	A
  12	A（A、B各1票，取最早达到该票数的候选人）
  15	A
  18	A
  19	C

2. 查询阶段 #

当输入目标时间时，在有序的快照数组中用二分查找找到小于等于目标时间的最大时间点，直接取出该时间点对应的候选人即可。比如输入20时，找到最大的<=20的时间是19，对应结果C，和示例一致。

复杂度分析 #

• 预处理：O(M logM)，主要来自对所有得票记录的排序，M为总得票数。
• 查询：O(logM)，仅需一次二分查找，这是理论上的最优查询效率。

对比你的原方案 #

你当前用Map<String, List>存储候选人的时间和票数，每次查询需要遍历所有候选人，对每个候选人的时间列表做二分统计票数，时间复杂度为O(N logK)（N为候选人数量，K为单个候选人的得票数）。当候选人数量较多时，这个效率远低于O(logM)的快照查询方案。

动态场景扩展（可选） #

如果数据集是动态的（会不断新增得票记录），可以在每次新增票时，更新当前状态并追加新的时间快照到有序结构中，查询逻辑保持不变，依然是O(logM)的时间复杂度。

内容的提问来源于stack exchange，提问作者Shobhit Mittal