911 Online Election
Last updated
Was this helpful?
Last updated
Was this helpful?
In an election, thei
-th vote was cast forpersons[i]
at timetimes[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 timet
.
Votes cast at timet
will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.
Example 1:
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]
.
(1) HashMap + Binary Search
思路: 对于给定times数组,我们需要做的就是对于times数组里每个对应的时间点,找到对应的winner是谁,这个可以直接用hashmap完成。而对于调用q()这个函数时,我们需要知道的是,对于任意的时刻t,我们要根据我们已知的times数组上的时间,用二分法找到不大于t的最大的时间。
HashMap + Binary Search: 时间复杂度: Constructor O(n), q(): O(logn), n是输入数组persons的长度,即人数。空间复杂度: O(n)