Algorithm
Problem Name: 911. Online Election
Problem Link: https://leetcode.com/problems/online-election/
You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i].
For each query at a time t, find 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.
Implement the TopVotedCandidate class:
TopVotedCandidate(int[] persons, int[] times)Initializes the object with thepersonsandtimesarrays.int q(int t)Returns the number of the person that was leading the election at timetaccording to the mentioned rules.
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 TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]); topVotedCandidate.q(3); // return 0, At time 3, the votes are [0], and 0 is leading. topVotedCandidate.q(12); // return 1, At time 12, the votes are [0,1,1], and 1 is leading. topVotedCandidate.q(25); // return 1, At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.) topVotedCandidate.q(15); // return 0 topVotedCandidate.q(24); // return 0 topVotedCandidate.q(8); // return 1
Constraints:
1 <= persons.length <= 5000times.length == persons.length0 <= persons[i] < persons.length0 <= times[i] <= 109timesis sorted in a strictly increasing order.times[0] <= t <= 109- At most
104calls will be made toq.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int *persons;
int *times;
int sz;
int votes[5001]; // number of votes per person
int top_v; // number of top votes at present
int top_p; // person who has top votes at present
int leader[5001]; // leader who has top votes at i-th time
int idx; // start index to continue to count
} TopVotedCandidate;
TopVotedCandidate* topVotedCandidateCreate(int* persons, int personsSize, int* times, int timesSize) {
TopVotedCandidate *obj = calloc(1, sizeof(TopVotedCandidate));
//assert(obj);
obj->persons = persons;
obj->times = times;
obj->sz = personsSize;
return obj;
}
int topVotedCandidateQ(TopVotedCandidate* obj, int t) {
int p, v, i, j, m;
while (obj->idx < obj->sz && obj->times[obj->idx] <= t) {
p = obj->persons[obj->idx];
v = ++ (obj->votes[p]);
if (obj->top_v < = v) {
obj->top_v = v;
obj->top_p = p;
}
obj->leader[obj->idx] = obj->top_p;
obj->idx ++;
}
i = obj->idx - 1;
while (obj->times[i] > t) {
i --; // use binary search to optimize
}
return obj->leader[i];
}
void topVotedCandidateFree(TopVotedCandidate* obj) {
free(obj);
}
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]
#2 Code Example with C++ Programming
Code -
C++ Programming
class TopVotedCandidate {
public:
TopVotedCandidate(vector<int> persons, vector<int> times) {
int curLead = -1;
unordered_map < int, int>count;
for (int i = 0; i < times.size(); ++i) {
count[persons[i]]++;
if(count[persons[i]] >= count[curLead]) {
curLead = persons[i];
}
m[times[i]] = curLead;
}
}
int q(int t) {
return (--m.upper_bound(t))->second;
}
private:
map < int, int>m;
};
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]
#3 Code Example with Java Programming
Code -
Java Programming
class TopVotedCandidate {
private TreeMap currWinner;
public TopVotedCandidate(int[] persons, int[] times) {
this.currWinner = new TreeMap < >();
Map candidateToVotecount = new HashMap<>();
int currWinningCandidate = -1;
for (int i = 0; i < persons.length; i++) {
int person = persons[i];
int newVoteCount = candidateToVotecount.getOrDefault(person, 0) + 1;
candidateToVotecount.put(person, newVoteCount);
if (currWinningCandidate == -1 || newVoteCount >= candidateToVotecount.get(currWinningCandidate)) {
currWinningCandidate = person;
}
currWinner.put(times[i], currWinningCandidate);
}
}
public int q(int t) {
return this.currWinner.floorEntry(t).getValue();
}
}
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]
#4 Code Example with Python Programming
Code -
Python Programming
class TopVotedCandidate:
def __init__(self, persons, times):
votes = collections.defaultdict(int)
winner = 0
self.winners = [None] * len(times)
self.times = times
for i, person in enumerate(persons):
votes[person] += 1
if votes[person] >= votes[winner]:
winner = person
self.winners[i] = winner
def q(self, t):
return self.winners[bisect.bisect(self.times, t) - 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]