# 0911. 在线选举

## 题目地址(911. 在线选举)

<https://leetcode-cn.com/problems/online-election/>

## 题目描述

```
在选举中，第 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 为数组长度。