题目描述

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

算法

(答案预处理+二分查找) $O(n + q\log n)$

1. 首先我们可以在一次扫描计算出每个时间点 time[i] 的当选者。因为每次票数只会增加 1，所以我们可以根据上一个时间点的当选者来推出当前时间的当选者。
2. 然后每询问一个时间，二分查找小于等于查询时间的时间点，返回该时间点的当选者。

时间复杂度

• 步骤 1 只需要线性时间；步骤 2 可以通过二分查找，故总时间复杂度为 $O(n + q\log n)$。

C++ 代码

class TopVotedCandidate {
public:
    int n;
    vector<int> vote;
    vector<int> ti;
    TopVotedCandidate(vector<int> persons, vector<int> times) {
        n = persons.size();
        vector<int> sum(n + 1, 0);
        vote = vector<int>(n);

        sum[persons[0]]++;
        vote[0] = persons[0];

        for (int i = 1; i < n; i++) {
            sum[persons[i]]++;
            if (sum[persons[i]] >= sum[vote[i - 1]])
                vote[i] = persons[i];
            else
                vote[i] = vote[i - 1];
        }

        ti = times;
    }

    int q(int t) {
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (t < ti[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return vote[l];
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */