0911. Online Election¶
题目信息¶
- 题号:
0911
- 难度:
Medium
- 主题:
设计题、按时间查询、票数领先者
- 原题:
- 重点:
构造时按严格递增的时间接收选票;查询只统计不晚于
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。