力扣每日一题2021-12-11在线选举

• 911.在线选举
• • 题目描述
  • 思路
  • • 二分查找
    • • Java实现
      • Python实现

在线选举

因为是在线查询，因此在初始化时就统计所有投票时刻的计票结果，如果查询投票时刻之间的时刻，则答案就是上一个投票时刻的答案。

class TopVotedCandidate {
    private int[] times;
    private int[] ans;
    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        ans = new int[times.length];
        int[] cnts = new int[times.length];
        int cur = -1;
        for(int i=0;i= cnts[cur])
                cur = persons[i];
            ans[i] = cur;
        }
    }
    
    public int q(int t) {
        int l = 0, r = times.length;
        while(l 
Python实现 
 
class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        n = len(times)
        cnts, cur = defaultdict(int), None
        self.ans, self.times = [-1] * n, times
        for i in range(n):
            cnts[persons[i]] += 1
            if cur is None or cnts[persons[i]] >= cnts[cur]:
                cur = persons[i]
            self.ans[i] = cur


    def q(self, t: int) -> int:
        return self.ans[bisect_right(self.times, t) - 1]



# Your TopVotedCandidate object will be instantiated and called as such:
# obj = TopVotedCandidate(persons, times)
# param_1 = obj.q(t)