第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0911. 在线选举

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

题目描述

1
在选举中,第 i 张票是在时间为 times[i] 时投给 persons[i] 的。
2
3
现在,我们想要实现下面的查询函数: TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。
4
5
在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下,最近获得投票的候选人将会获胜。
6
7
示例:
8
9
输入:["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]]
10
输出:[null,0,1,1,0,0,1]
11
解释:
12
时间为 3,票数分布情况是 [0],编号为 0 的候选人领先。
13
时间为 12,票数分布情况是 [0,1,1],编号为 1 的候选人领先。
14
时间为 25,票数分布情况是 [0,1,1,0,0,1],编号为 1 的候选人领先(因为最近的投票结果是平局)。
15
在时间 15、24 和 8 处继续执行 3 个查询。
16
17
18
提示:
19
20
1 <= persons.length = times.length <= 5000
21
0 <= persons[i] <= persons.length
22
times 是严格递增的数组,所有元素都在 [0, 10^9] 范围中。
23
每个测试用例最多调用 10000 次 TopVotedCandidate.q。
24
TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]。
Copied!

前置知识

公司

  • 暂无

思路

题目给了一个 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) 区间的值,使用数组统计不方便,因此这里我使用哈希表进行统计。
核心代码:
1
class TopVotedCandidate:
2
3
def __init__(self, persons: List[int], times: List[int]):
4
vote_count = collections.defaultdict(int) # 哈希表统计每个人的票数信息
5
max_voted_person = -1
6
max_voted_count = 0
7
winner = []
8
# zip([1,2,3], [4,5,6]) 会返回 [[1,4], [2,5], [3,6]]
9
for p, t in zip(persons, times):
10
vote_count[p] += 1
11
if vote_count[p] >= max_voted_count:
12
max_voted_count = vote_count[p]
13
max_voted_person = p
14
# 更新 winner
15
winner.append(max_voted_person)
Copied!
经过上面的处理生成了一个 winner 数组,winner 数组和 times 以及 persons 是等长的。
接下来就是查询了,查询的 api 如下:
1
q(int t) -> int
Copied!
我们要做的就是使用 t 去前面生成好的 winner 数组找。由于 times 是有序的,因此查询过程我们就可以使用二分了。
比如:
1
times = [2,4,5,6]
2
winner = [1,2,1,1]
Copied!
表示的就是:
  • 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 的前一个。关于最左插入我在二分查找 进行了详细的描述,不懂的可以看下。

关键点解析

  • 使用哈希表记录 times 中每一个时刻的优胜信息
  • 最左插入模板

代码

代码支持: Python3
1
class TopVotedCandidate:
2
3
def __init__(self, persons: List[int], times: List[int]):
4
vote_count = collections.defaultdict(int)
5
max_voted_person = -1
6
max_voted_count = 0
7
winner = []
8
for p, t in zip(persons, times):
9
vote_count[p] += 1
10
if vote_count[p] >= max_voted_count:
11
max_voted_count = vote_count[p]
12
max_voted_person = p
13
winner.append(max_voted_person)
14
self.winner = winner
15
self.times = times
16
17
def q(self, t: int) -> int:
18
winner = self.winner
19
# times 是不重复的,也就是严格递增的,类似 [2,4,5,6],这是关键
20
# eg:
21
# times [2,4,5,6]
22
# winner [1,2,1,1]
23
i = bisect.bisect_left(self.times, t)
24
if i != len(self.times) and self.times[i] == t:
25
return winner[i]
26
return winner[i - 1]
Copied!
复杂度分析
  • 时间复杂度:初始化的时间复杂度为 $O(N)$,q 的复杂度为 $O(logN)$,其中 N 为数组长度。
  • 空间复杂度:我们使用了 vote_count 记录投票情况,因此空间复杂度 $O(N)$,其中 N 为数组长度。