在选举中，第 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 <= 50000 <= persons[i] <= persons.lengthtimes是严格递增的数组，所有元素都在[0, 10^9]范围中。- 每个测试用例最多调用
10000次TopVotedCandidate.q。 TopVotedCandidate.q(int t)被调用时总是满足t >= times[0]。
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
self.times = times
mx, cur_win, n = -1, -1, len(persons)
counter = [0] * (n + 1)
self.win_persons = [0] * n
for i, p in enumerate(persons):
counter[p] += 1
if counter[p] >= mx:
mx = counter[p]
cur_win = p
self.win_persons[i] = cur_win
def q(self, t: int) -> int:
left, right = 0, len(self.win_persons) - 1
while left < right:
mid = (left + right + 1) >> 1
if self.times[mid] <= t:
left = mid
else:
right = mid - 1
return self.win_persons[left]
# Your TopVotedCandidate object will be instantiated and called as such:
# obj = TopVotedCandidate(persons, times)
# param_1 = obj.q(t)class TopVotedCandidate {
private int[] times;
private int[] winPersons;
public TopVotedCandidate(int[] persons, int[] times) {
this.times = times;
int mx = -1, curWin = -1;
int n = persons.length;
int[] counter = new int[n + 1];
winPersons = new int[n];
for (int i = 0; i < n; ++i) {
if (++counter[persons[i]] >= mx) {
mx = counter[persons[i]];
curWin = persons[i];
}
winPersons[i] = curWin;
}
}
public int q(int t) {
int left = 0, right = winPersons.length - 1;
while (left < right) {
int mid = (left + right + 1) >> 1;
if (times[mid] <= t) {
left = mid;
} else {
right = mid - 1;
}
}
return winPersons[left];
}
}
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* TopVotedCandidate obj = new TopVotedCandidate(persons, times);
* int param_1 = obj.q(t);
*/class TopVotedCandidate {
public:
vector<int> times;
vector<int> winPersons;
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
this->times = times;
int mx = -1, curWin = -1;
int n = persons.size();
vector<int> counter(n + 1);
winPersons.resize(n);
for (int i = 0; i < n; ++i)
{
if (++counter[persons[i]] >= mx)
{
mx = counter[persons[i]];
curWin = persons[i];
}
winPersons[i] = curWin;
}
}
int q(int t) {
int left = 0, right = winPersons.size() - 1;
while (left < right)
{
int mid = (left + right + 1) >> 1;
if (times[mid] <= t) left = mid;
else right = mid - 1;
}
return winPersons[left];
}
};
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
* int param_1 = obj->q(t);
*/type TopVotedCandidate struct {
times []int
winPersons []int
}
func Constructor(persons []int, times []int) TopVotedCandidate {
mx, curWin, n := -1, -1, len(persons)
counter := make([]int, n+1)
winPersons := make([]int, n)
for i, p := range persons {
counter[p]++
if counter[p] >= mx {
mx = counter[p]
curWin = p
}
winPersons[i] = curWin
}
return TopVotedCandidate{
times, winPersons,
}
}
func (this *TopVotedCandidate) Q(t int) int {
left, right := 0, len(this.winPersons)-1
for left < right {
mid := (left + right + 1) >> 1
if this.times[mid] <= t {
left = mid
} else {
right = mid - 1
}
}
return this.winPersons[left]
}
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* obj := Constructor(persons, times);
* param_1 := obj.Q(t);
*/