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.
class { vector<vector<int>> votes; vector<int> spersons; vector<int> stimes; boolcompPosition(int cur, int com, int start){ for(int i = start; i >= 0; i--){ if(spersons[i] == cur) returnfalse; if(spersons[i] == com) returntrue; } returnfalse; } public: TopVotedCandidate(vector<int> persons, vector<int> times) { int size = times.size(); stimes = times; spersons = persons; votes = vector<vector<int>>(size, vector<int>(size, 0)); vector<int> allVotes(size, 0); for(int i = 0; i < persons.size(); i++){ allVotes[persons[i]]++; votes[i] = allVotes; } }
intq(int t){ auto ind = lower_bound(stimes.begin(), stimes.end(), t); int curInd = (stimes[ind - stimes.begin()] == t) ? (ind - stimes.begin()) : (ind - stimes.begin() - 1 >= 0 ? ind - stimes.begin() - 1 : 0); vector<int> curVotes = votes[curInd]; // for(int v : curVotes) // cout << v << " "; // cout << endl; int maxV = 0; int res = 0; for(int i = curVotes.size()-1; i >= 0; i--){ if(curVotes[i] > maxV){ maxV = curVotes[i]; res = i; } elseif(curVotes[i] == maxV && compPosition(res, i, curInd)){ res = i; } } return res; } };
/** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate obj = new TopVotedCandidate(persons, times); * int param_1 = obj.q(t); */
/** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate obj = new TopVotedCandidate(persons, times); * int param_1 = obj.q(t); */
近期评论