https://leetcode.com/problems/online-election/
https://www.cnblogs.com/lightwindy/p/9758238.html
https://zhanghuimeng.github.io/post/leetcode-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.
Approach 2: Precomputed Answer + Binary Search
Intuition and Algorithm
As the votes come in, we can remember every event (winner, time) when the winner changes. After, we have a sorted list of these events that we can binary search for the answer.
- Time Complexity: , where is the number of votes, and is the number of queries.
class TopVotedCandidate {
List<Vote> A;
public TopVotedCandidate(int[] persons, int[] times) {
A = new ArrayList();
Map<Integer, Integer> count = new HashMap();
int leader = -1; // current leader
int m = 0; // current number of votes for leader
for (int i = 0; i < persons.length; ++i) {
int p = persons[i], t = times[i];
int c = count.getOrDefault(p, 0) + 1;
count.put(p, c);
if (c >= m) {
if (p != leader) { // lead change
leader = p;
A.add(new Vote(leader, t));
}
if (c > m) m = c;
}
}
}
public int q(int t) {
int lo = 1, hi = A.size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (A.get(mi).time <= t)
lo = mi + 1;
else
hi = mi;
}
return A.get(lo - 1).person;
}
}
class Vote {
int person, time;
Vote(int p, int t) {
person = p;
time = t;
}
}
Time complexity for constructor
TopVotedCandidate(int[] persons, int[] times) is O(nlogn), and for q(int t) is O(logn).private TreeMap<Integer, Integer> tm = new TreeMap<>(); // time and leading candidate
public TopVotedCandidate(int[] persons, int[] times) {
int[] count = new int[persons.length]; // count[i]: count of votes for persons[i].
for (int i = 0, max = -1; i < times.length; ++i) {
++count[persons[i]]; // at times[i], persons[i] got a vote.
if (max <= count[persons[i]]) { // is persons[i] leading?
max = count[persons[i]]; // update leading count.
tm.put(times[i], persons[i]); // update leading candidate.
}
}
}
public int q(int t) {
return tm.floorEntry(t).getValue(); // fetch the corresponding information.
}
Approach 1: List of Lists + Binary Search
We can store the votes in a list
A of lists of votes. Each vote has a person and a timestamp, and A[count] is a list of the count-th votes received for that person.
Then,
A[i][0] and A[i] are monotone increasing, so we can binary search on them to find the most recent vote by time.- Time Complexity: , where is the number of votes, and is the number of queries.
- Space Complexity: .
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class TopVotedCandidate {
List<List<Vote>> A;
public TopVotedCandidate(int[] persons, int[] times) {
A = new ArrayList();
Map<Integer, Integer> count = new HashMap();
for (int i = 0; i < persons.length; ++i) {
int p = persons[i], t = times[i];
int c = count.getOrDefault(p, 0) + 1;
count.put(p, c);
while (A.size() <= c)
A.add(new ArrayList<Vote>());
A.get(c).add(new Vote(p, t));
}
}
public int q(int t) {
// Binary search on A[i][0].time for smallest i
// such that A[i][0].time > t
int lo = 1, hi = A.size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (A.get(mi).get(0).time <= t)
lo = mi + 1;
else
hi = mi;
}
int i = lo - 1;
// Binary search on A[i][j].time for smallest j
// such that A[i][j].time > t
lo = 0;
hi = A.get(i).size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (A.get(i).get(mi).time <= t)
lo = mi + 1;
else
hi = mi;
}
int j = Math.max(lo - 1, 0);
return A.get(i).get(j).person;
}
}
class Vote {
int person, time;
Vote(int p, int t) {
person = p;
time = t;
}
}
https://www.cnblogs.com/lightwindy/p/9758238.html
Give a vote list = [(a, 100), (b, 150), (a, 200)] # (name, timestamp) and time T. Find the highest number of votes (or anyone with the highest number of votes) at T
ex: T = 100 -> a, T = 150 -> a or b, T = 200 -> a
Followup1: give one more input K, find Top K votes at T
Followup2: the same vote list, K, but given the Top K votes list, find the time T.
For the first question, just travers the vote list and if vote.T <= T increment
the vote for person vote.Name. While doing that maximize the vote number.
(O(n*l) time, O(c*l) space, c is the number of candidates, l is average length of name)
the vote for person vote.Name. While doing that maximize the vote number.
(O(n*l) time, O(c*l) space, c is the number of candidates, l is average length of name)
follow-up 1: instead of maximizing one, keep the hashtable with votes[person] = no. votes
now, put that into a vector and find the k-th element (using e.g. quicksort's partion
method which is linear)
(O(n*l) time, O(c*l) space)
now, put that into a vector and find the k-th element (using e.g. quicksort's partion
method which is linear)
(O(n*l) time, O(c*l) space)
follow-up 2: I assume given are the top K candidates at a certain time T I have to find.
I have to keep all candidates sorted at each step and compare the top k of them with
the given list. The first part (keeping candidates sorted at each step) can be done
using a balanced binary-tree, so I have O(n*lg(n)+n*l) for creating and maintaining that tree.
(I will have to transpose the name into an integer, and have a nameId instead of the
string in the tree)
Then I would have k compare's per iteration, which is then O(k*n*lg(n)+n*l). the factor k
I can get rid of if I implement the tree in a way, so I monitor when elements enter and
leave the top k. If one of the desired candidates enters top k, I reduce the amount of
candidates I need in top k, if one leaves, I increment back. If that counter (which
starts with k) is 0 I'm done, I found the first time where the desired condition happend.
I have to keep all candidates sorted at each step and compare the top k of them with
the given list. The first part (keeping candidates sorted at each step) can be done
using a balanced binary-tree, so I have O(n*lg(n)+n*l) for creating and maintaining that tree.
(I will have to transpose the name into an integer, and have a nameId instead of the
string in the tree)
Then I would have k compare's per iteration, which is then O(k*n*lg(n)+n*l). the factor k
I can get rid of if I implement the tree in a way, so I monitor when elements enter and
leave the top k. If one of the desired candidates enters top k, I reduce the amount of
candidates I need in top k, if one leaves, I increment back. If that counter (which
starts with k) is 0 I'm done, I found the first time where the desired condition happend.
struct Vote{ int time_; string name_;}string find_top_at_time(const vector<Vote>& votes, int time) { unordered_map<string, int> votes_per_name; string max_votes_name; int max_votes_count = -1; for (const Vote& vote : votes) { // O(n) if (vote.time_ <= time) { auto it = votes_per_name.find(vote.name_); // O(l) if (it == votes_per_name.end()) { it = votes_per_name.insert({ vote.name_, 0 }).first; // O(l) compensated } it->second++; if (it->second > max_votes_count) { max_votes_count = it->second; max_votes_name = vote.name_; // O(l) } } } return max_votes_name;} |
https://zhanghuimeng.github.io/post/leetcode-911-online-election/
