# 911. Online Election

In an election, the `i`-th vote was cast for `persons[i]` at time `times[i]`.

Now, we would like to implement the following query function: `TopVotedCandidate.q(int t)` will return the number of the person that was leading the election at time `t`.

Votes cast at time `t` will count towards our query.  In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

``````Input: ["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]]
Output: [null,0,1,1,0,0,1]
Explanation:
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.
``````

Note:

1. `1 <= persons.length = times.length <= 5000`
2. `0 <= persons[i] <= persons.length`
3. `times` is a strictly increasing array with all elements in `[0, 10^9]`.
4. `TopVotedCandidate.q` is called at most `10000` times per test case.
5. `TopVotedCandidate.q(int t)` is always called with `t >= times[0]`.

``````class TopVotedCandidate {
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
int n = persons.size(), lead = 0;
vector<int> count(n + 1);
for (int i = 0; i < n; ++i) {
}
}
}
int q(int t) {
return (--m.upper_bound(t))->second;
}

private:
map<int, int> m;
};
``````

``````class TopVotedCandidate {
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
int n = persons.size(), lead = 0;
vector<int> count(n + 1);
this->times = times;
for (int i = 0; i < n; ++i) {
}
}
}
int q(int t) {
int left = 0, right = times.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (times[mid] <= t) left = mid + 1;
else right = mid;
}
return m[times[right - 1]];
}

private:
unordered_map<int, int> m;
vector<int> times;
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/911

https://leetcode.com/problems/online-election/

https://leetcode.com/problems/online-election/discuss/173382/C%2B%2BJavaPython-Binary-Search-in-Times

https://leetcode.com/problems/online-election/discuss/191898/Anybody-has-a-magic-general-formula-for-Binary-Search

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation