911. Online Election
hashmap + treeMap
T: O(nlogn)
S: O(n)
T: O(n) times to build HashMap and TreeMap,
1. TreeMap insert is O(logn), so build TreeMap is O(nlogn)
2. HashMap insert is O(1), so build TreeMap is O(n)
And Query:
1. O(logn) to query TreeMap (floorKey())
2. get(key) is O(1)
class TopVotedCandidate {
private TreeMap<Integer, Integer> timeResult;
private Map<Integer, Integer> personVoteCount;
private int curLeader = -1;
private int curMax = -1;
public TopVotedCandidate(int[] persons, int[] times) {
timeResult = new TreeMap<>();
personVoteCount = new HashMap<>();
timeResult.put(-1, -1);
for (int i = 0; i < persons.length; i++) {
int person = persons[i];
int votes = personVoteCount.getOrDefault(person, 0)+1;
personVoteCount.put(person, votes);
if (votes >= curMax) {
curMax = votes;
curLeader = person;
}
timeResult.put(times[i], curLeader);
}
}
public int q(int t) {
Integer time = timeResult.floorKey(t);
if (time == null) {
return -1;
}
return timeResult.get(time);
}
}
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* TopVotedCandidate obj = new TopVotedCandidate(persons, times);
* int param_1 = obj.q(t);
notice, can't store entire HashMap in timeResult -> for all count info -> this becomes n^2 space!
but we only need cadidate results
T: O(n) times to build HashMap and TreeMap,
1. TreeMap insert is O(logn), so build TreeMap is O(nlogn)
2. HashMap insert is O(1), so build TreeMap is O(n)
And Query:
1. O(logn) to query TreeMap (floorKey())
2. get(key) is O(1)
*/hashmap + treeMap
T: O(nlogn)
S: O(n)
hashmap + bs
T: O(nlogn)
S: O(n)
better structure
Previous1011. Capacity To Ship Packages Within D DaysNext1482. Minimum Number of Days to Make m Bouquets
Last updated
Was this helpful?