多次查找

变化中多次查询

911. 在线选举 mid

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

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

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

实现 TopVotedCandidate 类：

• TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
• int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

其中, times 严格递增, persions[i] < n

记录候选人变化的时刻, 时刻 => 候选人

class TopVotedCandidate {
    TreeMap<Integer, Integer> map = new TreeMap<>();

    public TopVotedCandidate(int[] persons, int[] times) {
        // 记录排名变化的时刻, 时刻 => 候选人
        int n = persons.length;
        int[] cnt = new int[n];
        int maxVote = 0;
        for (int i = 0; i < n; i++) {
            int p = persons[i];
            int c = ++cnt[p];
            if (c >= maxVote) {
                maxVote = c;
                map.put(times[i], p);
            }
        }
    }

    public int q(int t) {
        return map.floorEntry(t).getValue();
    }
}