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 the persons and times arrays.
int q(int t) Returns the number of the person that was leading the election at time t 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] <= 109
times is sorted in a strictly increasing order.
times[0] <= t <= 109
At most 104 calls will be made to q.
Solutions
Solution 1: Binary Search
We can record the winner at each moment during initialization, and then use binary search to find the largest moment less than or equal to $t$ during the query, and return the winner at that moment.
During initialization, we use a counter $cnt$ to record the votes of each candidate, and a variable $cur$ to record the current leading candidate. Then we traverse each moment, update $cnt$ and $cur$, and record the winner at each moment.
During the query, we use binary search to find the largest moment less than or equal to $t$, and return the winner at that moment.
In terms of time complexity, during initialization, we need $O(n)$ time, and during the query, we need $O(\log n)$ time. The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 9101112131415161718192021
classTopVotedCandidate:def__init__(self,persons:List[int],times:List[int]):cnt=Counter()self.times=timesself.wins=[]cur=0forpinpersons:cnt[p]+=1ifcnt[cur]<=cnt[p]:cur=pself.wins.append(cur)defq(self,t:int)->int:i=bisect_right(self.times,t)-1returnself.wins[i]# Your TopVotedCandidate object will be instantiated and called as such:# obj = TopVotedCandidate(persons, times)# param_1 = obj.q(t)
classTopVotedCandidate{privateint[]times;privateint[]wins;publicTopVotedCandidate(int[]persons,int[]times){intn=persons.length;wins=newint[n];this.times=times;int[]cnt=newint[n];intcur=0;for(inti=0;i<n;++i){intp=persons[i];++cnt[p];if(cnt[cur]<=cnt[p]){cur=p;}wins[i]=cur;}}publicintq(intt){inti=Arrays.binarySearch(times,t+1);i=i<0?-i-2:i-1;returnwins[i];}}/** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate obj = new TopVotedCandidate(persons, times); * int param_1 = obj.q(t); */
classTopVotedCandidate{public:TopVotedCandidate(vector<int>&persons,vector<int>×){intn=persons.size();this->times=times;wins.resize(n);vector<int>cnt(n);intcur=0;for(inti=0;i<n;++i){intp=persons[i];++cnt[p];if(cnt[cur]<=cnt[p]){cur=p;}wins[i]=cur;}}intq(intt){inti=upper_bound(times.begin(),times.end(),t)-times.begin()-1;returnwins[i];}private:vector<int>times;vector<int>wins;};/** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate* obj = new TopVotedCandidate(persons, times); * int param_1 = obj->q(t); */
typeTopVotedCandidatestruct{times[]intwins[]int}funcConstructor(persons[]int,times[]int)TopVotedCandidate{n:=len(persons)wins:=make([]int,n)cnt:=make([]int,n)cur:=0fori,p:=rangepersons{cnt[p]++ifcnt[cur]<=cnt[p]{cur=p}wins[i]=cur}returnTopVotedCandidate{times,wins}}func(this*TopVotedCandidate)Q(tint)int{i:=sort.SearchInts(this.times,t+1)-1returnthis.wins[i]}/** * Your TopVotedCandidate object will be instantiated and called as such: * obj := Constructor(persons, times); * param_1 := obj.Q(t); */
classTopVotedCandidate{privatetimes:number[];privatewins:number[];constructor(persons:number[],times:number[]){constn=persons.length;this.times=times;this.wins=newArray<number>(n).fill(0);constcnt:Array<number>=newArray<number>(n).fill(0);letcur=0;for(leti=0;i<n;++i){constp=persons[i];cnt[p]++;if(cnt[cur]<=cnt[p]){cur=p;}this.wins[i]=cur;}}q(t:number):number{constsearch=(t:number):number=>{letl=0,r=this.times.length;while(l<r){constmid=(l+r)>>1;if(this.times[mid]>t){r=mid;}else{l=mid+1;}}returnl;};consti=search(t)-1;returnthis.wins[i];}}/** * Your TopVotedCandidate object will be instantiated and called as such: * var obj = new TopVotedCandidate(persons, times) * var param_1 = obj.q(t) */