# 911. Online Election

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]`

.

#### Here’s my rejected solution

<?php class TopVotedCandidate { public $dic=[]; public $r =[]; public $keys = []; /** * @param Integer[] $persons * @param Integer[] $times */ function __construct($persons, $times) { $max = 0; $prev_person = null; for($i = 0; $i < count($times); $i ++){ $this->inc($persons[$i]); arsort($this->$dic); foreach($this->$dic as $k=>$v){ $max_this_round = $k; break; } $person_this_round = $persons[$i]; if($i > 0){ if($max_this_round === $max){ $person_this_round = $prev_person; } } echo $person_this_round; $this->$r[$times[$i]] = $person_this_round; $max = $max_this_round; $prev_person = $persons[$i]; } var_dump($this->$r); ksort($this->$r); var_dump($this->$r); $this->$keys = array_keys($this->$r); } /** * @param Integer $t * @return Integer */ function q($t) { $k = $this->binarySearch($t); return $this->$r[$k]; } function inc($p){ if(isset($this->$dic[$p])){ $this->$dic[$p] ++; } else { $this->$dic[$p] = 1; } } function binarySearch($x) { $arr = $this->$keys; $low = 0; $high = count($arr) - 1; while ($low <= $high) { // compute middle index $mid = floor(($low + $high) / 2); // element found at mid if($arr[$low] <= $x && $arr[$mid] >= $x && $mid - $low <= 1) { return $low; } if ($x < $arr[$mid]) { // search the left side of the array $high = $mid -1; } else { // search the right side of the array $low = $mid + 1; } echo "$low-$mid-$high\n"; } return false; } } /** * Your TopVotedCandidate object will be instantiated and called as such: * $obj = TopVotedCandidate($persons, $times); * $ret_1 = $obj->q($t); */ ?>

Here are the problems:

- Just like the previous problem, my PHP syntax is wrong, and the prev problem is accepted. I didn’t even ever question about the syntax
- And I wasted too much time on debugging, caused by syntax.
- And my modified binary search isn’t working
- And yes, that’s totally a mess

#### Here’s the my accepted solution

<?php class TopVotedCandidate { public $dic=[]; public $r =[]; public $keys = []; /** * @param Integer[] $persons * @param Integer[] $times */ function __construct($persons, $times) { $prev_max = 0; $prev_winner = null; for($i = 0; $i < count($times); $i ++){ $this->inc($persons[$i]); arsort($this->dic); reset($this->dic); $winner = key($this->dic); $max = $this->dic[$winner]; if($prev_winner !== null){ if($max == $prev_max){ $winner = $prev_winner; } } if($this->dic[$persons[$i]] == $this->dic[$winner]){ $winner = $persons[$i]; } $prev_max = max($prev_max, $max); $prev_winner = $winner; $this->r[$times[$i]] = $winner; } ksort($this->r); $this->keys = array_keys($this->r); } /** * @param Integer $t * @return Integer */ function q($t) { $k = $this->binarySearch($t); echo "$t => $k"; return $this->r[$k]; } function inc($p){ if(isset($this->dic[$p])){ $this->dic[$p] ++; } else { $this->dic[$p] = 1; } } // This is a modified binary search, finding the nearest smaller index // just like floorKey in Java's TreeMap function binarySearch($x) { $arr = $this->keys; $low = 0; $high = count($arr) - 1; if($x < $arr[$low]){ return false; } while ($high >= $low) { $mid = $low + floor(($high - $low) / 2); if($x >= $arr[$high]){ return (int) $arr[$high]; } if($arr[$mid] == $x) { return (int) $arr[$mid]; } if ($x < $arr[$mid]) { $high = $mid-1; } else { $low = $mid+1; } } return (int) $arr[$low-1]; } } ?> /** * Your TopVotedCandidate object will be instantiated and called as such: * $obj = TopVotedCandidate($persons, $times); * $ret_1 = $obj->q($t); */

## 0 Comments