Leetcode 911 Online Election

发表于 |

在选举中，第 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. 1 <= persons.length = times.length <= 5000
  2. 0 <= persons[i] <= persons.length
  3. times 是严格递增的数组，所有元素都在 [0, 10^9] 范围中。
  4. 每个测试用例最多调用 10000 次 TopVotedCandidate.q。
  5. TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]。

题意分析：
给定一系列的时间点，在每个时间点会投出一票，在每个时间点都会有票数最高的人存在，现在有若干次询问，需要我们给询问的时间点票数最高的人

思路：
显然我们可以将初始给定的每个时间点的得票数最高的人记录下来，对于上面的例子有：
Q = {0:0, 5:1, 10:1, 15:0, 20:0, 25:1, 30:0}
然后对于问询的时间点t，我们只需要在Q中找到第一个比t小的时间点即可，显然是二分法！
由于t会比较大，所以可能存在大量重复问询，所以还需要用到缓存机制！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class TopVotedCandidate(object):

    def __init__(self, persons, times):
        maxCount = 0
        d = collections.defaultdict(int)
        self.Q = {}
        self.cache = {}
        for i in range(len(persons)):
            d[persons[i]] += 1
            if d[persons[i]] >= maxCount:
                maxCount = d[persons[i]]
                self.Q[times[i]] = persons[i]
        self.res = sorted(self.Q.keys())

    def q(self, t):
        if t not in self.cache:
            index = bisect.bisect_right(self.res, t)
            self.cache[t] = self.Q[self.res[index-1]]
        return self.cache[t]