题目链接：911. 在线选举
预计算好每个时刻选中的人选，然后通过二分查找在每次查询时，迅速查找到对应的值。
from collections import defaultdict
from typing import List
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
c, voted, data = defaultdict(int), None, []
for p, t in zip(persons, times):
c[p] += 1
if voted is None or c[p] >= c[voted]:
voted = p
data.append((t, voted))
self._data = data
def q(self, t: int) -> int:
if len(self._data) == 0 or t < self._data[0][0]:
return -1
if t >= self._data[-1][0]:
return self._data[-1][1]
l, r = 0, len(self._data) - 1
while l < r:
mid = (l + r + 1) // 2
if self._data[mid][0] <= t:
l = mid
else:
r = mid - 1
return self._data[l][1]
二分查找也可以使用 python 内置的方法：
from bisect import bisect
from collections import defaultdict
from typing import List
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
c, voted, data = defaultdict(int), None, []
for p, t in zip(persons, times):
c[p] += 1
if voted is None or c[p] >= c[voted]:
voted = p
data.append(voted)
self._data, self._times = data, times
def q(self, t: int) -> int:
if len(self._data) == 0 or t < self._times[0]:
return -1
if t >= self._times[-1]:
return self._data[-1]
return self._data[bisect(self._times, t) - 1]