911. Online Election #

Problem #

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

Problem Summary #

In an election, the i-th vote was cast for persons[i] at time times[i].

Now, we want to implement the following query function: TopVotedCandidate.q(int t) will return the number of the candidate leading the election at time t.

Votes cast at time t will also be counted in our query. In the case of a tie, the candidate who most recently received a vote wins.

Note:

1. 1 <= persons.length = times.length <= 5000
2. 0 <= persons[i] <= persons.length
3. times is a strictly increasing array, and all elements are in the range [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].

Solution Approach #

• Given two arrays, representing the votes received by the i-th person at time t, respectively. We need to implement a query function that, for any time t, outputs whose votes are leading.
• The persons[] array contains the IDs of the people who received votes, and the times[] array contains the corresponding time of each vote. The times[] array is sorted by default in ascending order. First calculate who is leading in votes at each time and store it in an array. When implementing the query function, we only need to binary search the times[] array to find the largest time i that is less than or equal to the query time t, then output the ID of the person leading at the corresponding time from the array of vote leaders.

Code #

package leetcode

import (
	"sort"
)

// TopVotedCandidate define
type TopVotedCandidate struct {
	persons []int
	times   []int
}

// Constructor911 define
func Constructor911(persons []int, times []int) TopVotedCandidate {
	leaders, votes := make([]int, len(persons)), make([]int, len(persons))
	leader := persons[0]
	for i := 0; i < len(persons); i++ {
		p := persons[i]
		votes[p]++
		if votes[p] >= votes[leader] {
			leader = p
		}
		leaders[i] = leader
	}
	return TopVotedCandidate{persons: leaders, times: times}
}

// Q define
func (tvc *TopVotedCandidate) Q(t int) int {
	i := sort.Search(len(tvc.times), func(p int) bool { return tvc.times[p] > t })
	return tvc.persons[i-1]
}

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