911. 在线选举

给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
int q(int 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]

解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1

提示：

1 <= persons.length <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 109
times 是一个严格递增的有序数组
times[0] <= t <= 109
每个测试用例最多调用 104 次 q

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/online-election
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

from leetcode_python.utils import *
import bisect

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        cnt = defaultdict(int)
        time_top = []
        maxp = 0
        for p,t in zip(persons,times):
            cnt[p]+=1
            if cnt[p]>=cnt[maxp]:
                maxp = p
            time_top.append((t,maxp))
        self.time_top = time_top
        self.length = len(persons)
        print(time_top)

    def q(self, t: int) -> int:
        left,right=0,self.length-1
        if t>=self.time_top[-1][0]:return self.time_top[-1][1]
        while left<right:
            midid = left+(right-left)//2
            midt = self.time_top[midid][0]
            if midt==t:return self.time_top[midid][1]
            elif midt<t:
                left = midid
            else:
                right = midid
            # print(t,left,right,midt)
            if right-left==1 and self.time_top[right][0]>t:return self.time_top[left][1]
        return self.time_top[left][0]

    def q_官方(self, t: int) -> int:
        l, r = 0, self.length - 1
        while l < r:
            m = l + (r - l + 1) // 2
            if self.time_top[m][0] <= t:
                l = m
            else:
                r = m - 1
        # 也可以使用内置的二分查找的包来确定 l
        l = bisect.bisect(self.times, t) - 1
        return self.time_top[l][1]



def test(data_test):
    s = TopVotedCandidate()
    data = data_test  # normal
    # data = [list2node(data_test[0])]  # list转node
    return s.getResult(*data)


def test_obj(data_test):
    result = [None]
    obj = TopVotedCandidate(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        # [["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]]],
        # [["TopVotedCandidate","q","q","q","q","q","q","q","q","q","q"],[[[0,0,0,0,1],[0,6,39,52,75]],[45],[49],[59],[68],[42],[37],[99],[26],[78],[43]]],
        # [["TopVotedCandidate","q"],[[[0,0,0,0,1],[0,6,39,52,75]],[45]]],
        [["TopVotedCandidate","q","q","q","q","q","q","q","q","q","q"],[[[0,1,0,1,1],[24,29,31,76,81]],[28],[24],[29],[77],[30],[25],[76],[75],[81],[80]]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test_obj(data_test))
        print(f'use time:{time.time() - t0}s')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

备注：
GitHub：https://github.com/monijuan/leetcode_python

CSDN汇总：模拟卷Leetcode 题解汇总_卷子的博客-CSDN博客

可以加QQ群交流：1092754609

leetcode_python.utils详见汇总页说明
先刷的题，之后用脚本生成的blog，如果有错请留言，我看到了会修改的！谢谢！