Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/911.html
911. Online Election (Medium)
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 3, the votes are [0], and 0 is leading. At time 12, the votes are [0,1,1], and 1 is leading. 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 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times
is a strictly increasing array with all elements in[0, 10^9]
.TopVotedCandidate.q
is called at most10000
times per test case.TopVotedCandidate.q(int t)
is always called witht >= times[0]
.
Solution 1.

class TopVotedCandidate { private int[] times; private int[] wins; public TopVotedCandidate(int[] persons, int[] times) { int n = persons.length; int mx = 0, cur = 0; this.times = times; wins = new int[n]; int[] counter = new int[n]; for (int i = 0; i < n; ++i) { int p = persons[i]; if (++counter[p] >= mx) { mx = counter[p]; cur = p; } wins[i] = cur; } } public int q(int t) { int left = 0, right = wins.length  1; while (left < right) { int mid = (left + right + 1) >>> 1; if (times[mid] <= t) { left = mid; } else { right = mid  1; } } return wins[left]; } } /** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate obj = new TopVotedCandidate(persons, times); * int param_1 = obj.q(t); */

class TopVotedCandidate { public: vector<int> times; vector<int> wins; TopVotedCandidate(vector<int>& persons, vector<int>& times) { int n = persons.size(); wins.resize(n); int mx = 0, cur = 0; this>times = times; vector<int> counter(n); for (int i = 0; i < n; ++i) { int p = persons[i]; if (++counter[p] >= mx) { mx = counter[p]; cur = p; } wins[i] = cur; } } int q(int t) { int left = 0, right = wins.size()  1; while (left < right) { int mid = left + right + 1 >> 1; if (times[mid] <= t) left = mid; else right = mid  1; } return wins[left]; } }; /** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate* obj = new TopVotedCandidate(persons, times); * int param_1 = obj>q(t); */

class TopVotedCandidate: def __init__(self, persons: List[int], times: List[int]): mx = cur = 0 counter = Counter() self.times = times self.wins = [] for i, p in enumerate(persons): counter[p] += 1 if counter[p] >= mx: mx, cur = counter[p], p self.wins.append(cur) def q(self, t: int) > int: left, right = 0, len(self.wins)  1 while left < right: mid = (left + right + 1) >> 1 if self.times[mid] <= t: left = mid else: right = mid  1 return self.wins[left] # Your TopVotedCandidate object will be instantiated and called as such: # obj = TopVotedCandidate(persons, times) # param_1 = obj.q(t)

type TopVotedCandidate struct { times []int wins []int } func Constructor(persons []int, times []int) TopVotedCandidate { mx, cur, n := 0, 0, len(persons) counter := make([]int, n) wins := make([]int, n) for i, p := range persons { counter[p]++ if counter[p] >= mx { mx = counter[p] cur = p } wins[i] = cur } return TopVotedCandidate{times, wins} } func (this *TopVotedCandidate) Q(t int) int { left, right := 0, len(this.wins)1 for left < right { mid := (left + right + 1) >> 1 if this.times[mid] <= t { left = mid } else { right = mid  1 } } return this.wins[left] } /** * Your TopVotedCandidate object will be instantiated and called as such: * obj := Constructor(persons, times); * param_1 := obj.Q(t); */