### 题目

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 most 10000 times per test case.
TopVotedCandidate.q(int t) is always called with t >= times[0].
```

### 思路

题目其实挺简单，主要是理解题目的意思. 用一个数组存放每个时间点的winner, 然后再用二分法找出时间点的lower bound即可, 容易错的是一些boundary check

### Swift 题解

```
class TopVotedCandidate {
var result: [Int]
var times: [Int]
init(_ persons: [Int], _ times: [Int]) {
self.result = Array(repeating: -1, count: times.count)
var count = [Int: Int]()
var max = -1
for (index, person) in persons.enumerated() {
if let currentCount = count[person] {
count[person] = (currentCount + 1)
} else {
count[person] = 1
}
if count[person]! >= max {
max = count[person]!
result[index] = person
} else {
result[index] = result[index - 1]
}
}
self.times = times
}
func q(_ t: Int) -> Int {
var left = 0
var right = times.count - 1
while left <= right {
let middle = (left + right) / 2
let time = times[middle]
if time == t {
return result[middle]
} else if time > t {
right = middle - 1
if right > 0 {
if times[right] < t {
return result[right]
}
}
} else {
left = middle + 1
if left < times.count {
if times[left] > t {
return result[middle]
}
}
}
}
return left == times.count ? result.last! : -1
}
}
```