# 0911. 在线选举
## 题目地址(911. 在线选举)
## 题目描述
```
在选举中，第 i 张票是在时间为 times[i] 时投给 persons[i] 的。
现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。
在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
示例：
输入：["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
输出：[null,0,1,1,0,0,1]
解释：
时间为 3，票数分布情况是 [0]，编号为 0 的候选人领先。
时间为 12，票数分布情况是 [0,1,1]，编号为 1 的候选人领先。
时间为 25，票数分布情况是 [0,1,1,0,0,1]，编号为 1 的候选人领先（因为最近的投票结果是平局）。
在时间 15、24 和 8 处继续执行 3 个查询。
提示：
1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times 是严格递增的数组，所有元素都在 [0, 10^9] 范围中。
每个测试用例最多调用 10000 次 TopVotedCandidate.q。
TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]。
```
## 前置知识
* [二分查找](https://github.com/azl397985856/leetcode/blob/master/91/binary-search.md)
* 哈希表
## 公司
* 暂无
## 思路
题目给了一个 times 数组， 我们可以记录 times 中每一时刻 t 的优胜者，只需要边遍历边统计票数，用两个全局参数 max\_voted\_person 和 max\_voted\_count 分别表示当前票数最多的人和其对应的票数即可。
由于题目要求如果票数相同取最近的，那么只需要在更新 max\_voted\_person 和 max\_voted\_count 的时候，增加**如果当前人票数和 max\_voted\_count 一致也更新 max\_voted\_person 和 max\_voted\_count**逻辑即可轻松实现。
由于题目没有说 person\[i] 是 \[0, N) 区间的值，使用数组统计不方便，因此这里我使用哈希表进行统计。
核心代码：
```python
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
vote_count = collections.defaultdict(int) # 哈希表统计每个人的票数信息
max_voted_person = -1
max_voted_count = 0
winner = []
# zip([1,2,3], [4,5,6]) 会返回 [[1,4], [2,5], [3,6]]
for p, t in zip(persons, times):
vote_count[p] += 1
if vote_count[p] >= max_voted_count:
max_voted_count = vote_count[p]
max_voted_person = p
# 更新 winner
winner.append(max_voted_person)
```
经过上面的处理生成了一个 winner 数组，winner 数组和 times 以及 persons 是等长的。
接下来就是查询了，查询的 api 如下：
```python
q(int t) -> int
```
我们要做的就是使用 t 去前面生成好的 winner 数组找。由于 times 是有序的，因此查询过程我们就可以使用二分了。
比如:
```python
times = [2,4,5,6]
winner = [1,2,1,1]
```
表示的就是：
* 2，5，6 时刻的优胜者是 1
* 4 时刻优胜者是 2
如果 t 为 2， 4， 5， 6 我们直接返回 winner 对应的项目即可。比如 t 为 2，2 在 times 中 第 0 项，因此返回 winner\[0]即可。
如果 t 为 3 呢？3 不在 \[2,4,5,6] 中。根据题目要求，我们需要以 3 的最近的一个往前的时间点，也就是 2 ，我们仍然需要返回 winner\[0]。
总的来说，其实我们需要找的位置就是一个最左插入位置，即将 t 插入 times 之后仍然保持有序的位置。比如 t 为 3 就是 \[2,3,4,5,6]，我们需要返回 3 的前一个。关于最左插入我在[二分查找](https://github.com/azl397985856/leetcode/blob/master/91/binary-search.md) 进行了详细的描述，不懂的可以看下。
## 关键点解析
* 使用哈希表记录 times 中每一个时刻的优胜信息
* 最左插入模板
## 代码
代码支持： Python3
```python
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
vote_count = collections.defaultdict(int)
max_voted_person = -1
max_voted_count = 0
winner = []
for p, t in zip(persons, times):
vote_count[p] += 1
if vote_count[p] >= max_voted_count:
max_voted_count = vote_count[p]
max_voted_person = p
winner.append(max_voted_person)
self.winner = winner
self.times = times
def q(self, t: int) -> int:
winner = self.winner
# times 是不重复的，也就是严格递增的，类似 [2,4,5,6]，这是关键
# eg:
# times [2,4,5,6]
# winner [1,2,1,1]
i = bisect.bisect_left(self.times, t)
if i != len(self.times) and self.times[i] == t:
return winner[i]
return winner[i - 1]
```
**复杂度分析**
* 时间复杂度：初始化的时间复杂度为 $O(N)$，q 的复杂度为 $O(logN)$，其中 N 为数组长度。
* 空间复杂度：我们使用了 vote\_count 记录投票情况，因此空间复杂度 $O(N)$，其中 N 为数组长度。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/911.online-election.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.