Welcome to Subscribe On Youtube
911. Online Election
Description
You are given two integer arrays persons
and times
. In an election, the i^{th}
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 thepersons
andtimes
arrays.int q(int t)
Returns the number of the person that was leading the election at timet
according 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 <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 10^{9}
times
is sorted in a strictly increasing order.times[0] <= t <= 10^{9}
 At most
10^{4}
calls will be made toq
.
Solutions
Binary search.

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); */

class TopVotedCandidate { private times: number[]; private wins: number[]; constructor(persons: number[], times: number[]) { const n = persons.length; this.times = times; this.wins = new Array<number>(n).fill(0); const cnt: Array<number> = new Array<number>(n).fill(0); let cur = 0; for (let i = 0; i < n; ++i) { const p = persons[i]; cnt[p]++; if (cnt[cur] <= cnt[p]) { cur = p; } this.wins[i] = cur; } } q(t: number): number { const search = (t: number): number => { let l = 0, r = this.times.length; while (l < r) { const mid = (l + r) >> 1; if (this.times[mid] > t) { r = mid; } else { l = mid + 1; } } return l; }; const i = search(t)  1; return this.wins[i]; } } /** * Your TopVotedCandidate object will be instantiated and called as such: * var obj = new TopVotedCandidate(persons, times) * var param_1 = obj.q(t) */