911. Online Election

Version #2 Binary Search [TODO]


Version #1 TreeMap
Map + TreeMap
O(nlog) for initialization, O(logn) for query
62.40 %
class TopVotedCandidate {
    private TreeMap<Integer, Integer> map;
    public TopVotedCandidate(int[] persons, int[] times) {
        int max = 0;
        // k -> time, v -> maxPerson
        map = new TreeMap<>();
        // k -> person, v -> votes
        Map<Integer, Integer> votes = new HashMap<>();
        for (int i = 0; i < persons.length; i++) {
            int vote4Person = votes.getOrDefault(persons[i], 0) + 1;
            if (vote4Person >= max) {
                max = vote4Person;
                map.put(times[i], persons[i]);
            }
            votes.put(persons[i], vote4Person);
        }
    }
   
    public int q(int t) {
        return map.floorEntry(t).getValue();
    }
}