911-online-election.md

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]。

---

题目标签：Binary Search

题目链接：LeetCode / LeetCode中国

题解

比较简单，主要是要理解题意。

某次投票后到下次投票前，投票结果不变。因此，可以记录每次投票后的投票结果，然后查询时利用二分法定位，直接取之前最近一次的投票结果即可。

Language	Runtime	Memory
python3	408 ms	N/A

class TopVotedCandidate:

    def __init__(self, persons, times):
        """
        :type persons: List[int]
        :type times: List[int]
        """
        self.res = collections.OrderedDict()
        c = collections.defaultdict(int)
        best = {'person': None, 'vote': 0}
        for p, t in zip(persons, times):
            c[p] += 1
            if c[p] >= best['vote']:
                best['person'] = p
                best['vote'] = c[p]
            self.res[t] = best['person']
            # print(best)
        # print(self.res)
        self.res_keys = list(self.res.keys())

    def q(self, t):
        """
        :type t: int
        :rtype: int
        """
        # print(t, bisect.bisect_right(self.res_keys, t)-1)
        return self.res[self.res_keys[bisect.bisect_right(self.res_keys, t)-1]]


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