二分搜索（十一）911. 在线选举

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#include vector #include unordered_map #include algorithm using namespace std; class TopVotedCandidate { private: vectorint times; // 存时间点 vectorint winners; // winners[i] 代表在 times[i] 这个时刻的赢家 public: TopVotedCandidate(vectorint persons, vectorint times) { this-times times; unordered_mapint, int voteCounts; // 记录每个人的票数 int topCandidate -1; // 当前赢家 int topVotes 0; // 当前最高票数 // 1. 预处理遍历每一张选票 for (int i 0; i persons.size(); i) { int p persons[i]; voteCounts[p]; // 给他投一票 // 2. 更新赢家逻辑 // 题目规定票数相等时最近获得选票的人获胜。 // 因为我们是按时间顺序遍历的所以只要当前这个人的票数 当前最高票数 // 他就自动成为“最新的”赢家 if (voteCounts[p] topVotes) { topVotes voteCounts[p]; topCandidate p; } // 3. 记录这个时刻的赢家 winners.push_back(topCandidate); } } int q(int t) { // 4. 二分查找 // 我们要找 t 的最后一个时间点 // 使用 upper_bound 找到第一个 t 的位置 auto it upper_bound(times.begin(), times.end(), t); // 然后回退一步就是 t 的位置 int index prev(it)-times.begin(); // int index distance(times.begin(), it) - 1; return winners[index]; } }; /** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate* obj new TopVotedCandidate(persons, times); * int param_1 obj-q(t); */