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: vector<int> times; // 存时间点 vector<int> winners; // winners[i] 代表在 times[i] 这个时刻的赢家 public: TopVotedCandidate(vector<int>& persons, vector<int>& times) { this->times = times; unordered_map<int, 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); */
