当男生遇见女生：那些闪闪发光的化学反应

在线选举给你两个整数数组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(

; // 返回 0 在时刻 3 票数分布为 [0] 编号为 0 的候选人领先。

topVotedCandidate.q(

; // 返回 1 在时刻 12 票数分布为 [0,1,1] 编号为 1 的候选人领先。

topVotedCandidate.q(

; // 返回 1 在时刻 25 票数分布为 [0,1,1,0,0,1] 编号为 1 的候选人领先。

在平局的情况下1 是最近获得投票的候选人。

topVotedCandidate.q(

; // 返回 0 topVotedCandidate.q(

; // 返回 0 topVotedCandidate.q(

; // 返回 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; // 当前最高票数 //

预处理遍历每一张选票 for (int i 0; i persons.size(); i) { int p persons[i]; voteCounts[p]; // 给他投一票 //

更新赢家逻辑 // 题目规定票数相等时最近获得选票的人获胜。

// 因为我们是按时间顺序遍历的所以只要当前这个人的票数 当前最高票数 // 他就自动成为“最新的”赢家 if (voteCounts[p] topVotes) { topVotes voteCounts[p]; topCandidate p; } //

记录这个时刻的赢家 winners.push_back(topCandidate); } } int q(int t) { //

二分查找 // 我们要找 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); */

zzj中国zzj-zzj中国应用