forked from liuyubobobo/Play-Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main2.cpp
74 lines (55 loc) · 1.66 KB
/
main2.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/// Source : https://leetcode.com/problems/online-election/description/
/// Author : liuyubobobo
/// Time : 2018-09-22
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cassert>
using namespace std;
/// Using HashSet to precalculate the winner in every time
/// Using Binary Search to query
///
/// Time Complexity: init: O(n)
/// query: O(logn)
class TopVotedCandidate {
private:
vector<pair<int, int>> winner;
public:
TopVotedCandidate(vector<int> persons, vector<int> times) {
unordered_map<int, int> cnt; // person -> votes
int maxVote = 0;
int winID = -1;
winner.clear();
for(int i = 0; i < persons.size(); i ++){
cnt[persons[i]] ++;
if(cnt[persons[i]] >= maxVote){
maxVote = cnt[persons[i]];
winID = persons[i];
}
winner.push_back(make_pair(times[i], winID));
}
}
int q(int t) {
vector<pair<int, int>>::iterator iter =
lower_bound(winner.begin(), winner.end(), make_pair(t, -1));
if(iter->first != t){
assert(iter != winner.begin());
iter --;
}
return iter->second;
}
};
int main() {
vector<int> persons1 = {0,1,1,0,0,1,0};
vector<int> times1 = {0,5,10,15,20,25,30};
TopVotedCandidate topVotedCandidate1(persons1, times1);
cout << topVotedCandidate1.q(3) << endl;
// 0
vector<int> persons2 = {0,0,0,0,1};
vector<int> times2 = {0,6,39,52,75};
TopVotedCandidate topVotedCandidate2(persons2, times2);
cout << topVotedCandidate2.q(99) << endl;
// 0
return 0;
}