0911. Online Election

题目信息

题号:

0911

难度:

Medium

主题:

设计题、按时间查询、票数领先者

原题:

LeetCode 0911

重点:

构造时按严格递增的时间接收选票;查询只统计不晚于 t 的票,票数相同时由最近获得选票的候选人领先

题目重述

实现 TopVotedCandidate 类。构造函数接收等长数组 persons 和 times,第 i 张选票在时刻 times[i] 投给候选人 persons[i],并且 times 严格递增。

q(t) 返回在时刻 t 时的领先候选人,即只统计投票时间小于或等于 t 的选票。若多个候选人的票数并列最高,则最近获得一张选票的候选人领先。对象需要支持多次相互独立的时间查询。

1 <= persons.length <= 5000,0 <= persons[i] < persons.length,投票时间为非负整数;查询满足 times[0] <= t <= 10^9,调用 q 不超过 10^4 次。

自建示例

平票时由最近得票者领先:

输入:
["TopVotedCandidate","q","q"]
[[[1,2,2,1],[5,10,15,20]],[12],[20]]
输出:[null,2,1]
解释:时刻 12 时两人各一票,最近得票的是候选人 2;时刻 20 时两人各两票,最近得票的是候选人 1。

只有一张选票:

输入:
["TopVotedCandidate","q"]
[[[0],[7]],[7]]
输出:[null,0]
解释:唯一一张选票在时刻 7 投给候选人 0,查询该时刻时领先者只能是 0。