# 911 Online Election

## 911. [Online Election](https://leetcode.com/problems/online-election/description/)

## 1. Question

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. `1 <= persons.length = times.length <= 5000`
2. `0 <= persons[i] <= persons.length`
3. `times`is a strictly increasing array with all elements in`[0, 10^9]`.
4. `TopVotedCandidate.q`is called at most`10000`times per test case.
5. `TopVotedCandidate.q(int t)`is always called with`t >= times[0]`.

## 2. Implementation

**(1) HashMap + Binary Search**

思路: 对于给定times数组，我们需要做的就是对于times数组里每个对应的时间点，找到对应的winner是谁，这个可以直接用hashmap完成。而对于调用q()这个函数时，我们需要知道的是，对于任意的时刻t，我们要根据我们已知的times数组上的时间，**用二分法找到不大于t的最大的时间。**

```java
class TopVotedCandidate {
    Map<Integer, Integer> map = new HashMap(); // key： time, value : winner
    int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        map = new HashMap();
        this.times = times;

        int[] count = new int[persons.length];
        int winner = -1;

        for (int i = 0; i < times.length; i++) {
            ++count[persons[i]];

            if (map.isEmpty() || count[winner] <= count[persons[i]]) {
                winner = persons[i];
            }
            map.put(times[i], winner);
        }
    }

    public int q(int t) {
        int index = binarySearch(times, t);
        return map.get(times[index]);
    }

    public int binarySearch(int[] array, int key) {
        int start = 0, end = array.length - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;

            if (array[mid] > key) {
                end = mid - 1;
            }
            else {
                start = mid;
            }
        }
        return array[end] <= key ? end : start;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */
```

## 3. Time & Space Complexity

**HashMap + Binary Search:** 时间复杂度: Constructor O(n), q(): O(logn), n是输入数组persons的长度，即人数。空间复杂度: O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/911-online-election.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.