难度：★★★☆☆
类型：数据结构
方法：二分法
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
在选举中，第 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]。
解答
实际上只有两个问题需要考虑：
- 如何记录各个标志性时刻下的当前获胜者；
- 如何查询给定时刻的获胜者。
这两个问题，根据题目的函数定义格式，我们分别写在init函数和q函数中。
定义一个实例变量self.winner，这是一个列表，列表中记录各个标志时刻下的当前获胜者。这里的标志时刻，也就是输入的times列表，我们把它也存储在实例变量self.times中，查询函数中需要用。
时刻和当前被投票者是成对出现的，我们需要准备一个计票器变量votes_of_，该变量是一个字典，字典的键是各个候选人，值是各个候选人的得票。为了便于计算，我们用python中内置的default_dict实现，在简化表达的同时，省去了找不到键的困扰。我们还需要准备中间变量winner_by_now和max_ticket，用以记录当前获胜的选手及其选票。
按照时间顺序遍历各个投票事件，将当前候选人person的选票加一，同时需要及时的查看这个候选人是否已经达记录中曾经有过的最大选票值，一旦该候选人选票达到或超过max_ticket，则说明该候选人已经成为当前时刻的赢家，需要及时更新中间变量winner_by_now和max_ticket。
在查询函数q中，我们使用二分查找法，可以快速定位所查询的时间在记录中出现的位置，由于时刻列表与各个时刻对应的赢家是对应的，找到输入时间t对应于时间列表self.times中的合理位置，就可以根据这个位置快速找到该时刻对应的赢家。我们使用bisect可以快速实现二分法定位操作，注意返回的是插入位置，需要将该下标index-1才能作为当前查询时刻所在位置。
import bisect
from collections import defaultdict
class TopVotedCandidate:
def __init__(self, persons, times):
self.times = times
self.winner = []
votes_of_ = defaultdict(int)
winner_by_now = persons[0]
max_ticket = 0
for person in persons:
votes_of_[person] += 1
if votes_of_[person] >= max_ticket:
winner_by_now = person
max_ticket = votes_of_[person]
self.winner.append(winner_by_now)
def q(self, t):
index = bisect.bisect(self.times, t) - 1
return self.winner[index]
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论