Friday, September 25, 2020

LeetCode [911] Online Election

 911. Online Election

Medium

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].
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class TopVotedCandidate {
    class State{
        Map<Integer, Integer> votes;
        int leadingVote;
        int leadingPerson;
        State(int person){
            votes = new HashMap<>();
            votes.put(person, 1);
            leadingVote = 1;
            leadingPerson = person;
        }
        
        State(State s){
            votes = s.votes;
            leadingVote = s.leadingVote;
            leadingPerson = s.leadingPerson;
        }

        void update(int person){
            votes.put(person, votes.getOrDefault(person, 0)+1);
            if(votes.get(person)>=leadingVote){
                leadingVote = votes.get(person);
                leadingPerson = person;
            }
        }
    }

    TreeMap<Integer, State> map = new TreeMap<>();
    public TopVotedCandidate(int[] persons, int[] times) {
        State state0 = new State(persons[0]);
        map.put(times[0], state0);
        for(int i=1; i<persons.length; ++i){
            State state = new State(map.get(times[i-1]));
            state.update(persons[i]);
            map.put(times[i], state);
        }
    }
    
    public int q(int t) {
        Integer mostRecentTime = map.floorKey(t);
        State mostRecentState = mostRecentTime!=null ? map.get(mostRecentTime) : map.lastEntry().getValue();
        return mostRecentState.leadingPerson;
    }
}

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

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)