You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i].
For each query at a time t, find 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.
Implement the TopVotedCandidate class:
TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
int q(int t) Returns the number of the person that was leading the election at time t according to the mentioned rules.
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
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // return 0, At time 3, the votes are [0], and 0 is leading.
topVotedCandidate.q(12); // return 1, At time 12, the votes are [0,1,1], and 1 is leading.
topVotedCandidate.q(25); // return 1, At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
topVotedCandidate.q(15); // return 0
topVotedCandidate.q(24); // return 0
topVotedCandidate.q(8); // return 1
Constraints:
1 <= persons.length <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 109
times is sorted in a strictly increasing order.
times[0] <= t <= 109
At most 104 calls will be made to q.
在线选举。
给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
实现 TopVotedCandidate 类：
TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。
思路
这是一道设计题。这里我重新解释一下题意。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的，这个部分应该没有歧义。但是接下来，对于发生在时刻 t 的每个查询，请注意这个时刻 t 未必跟投票的时刻是能对的上的。比如题目给的例子，如下是分别在时间点 0, 5, 10, 15, 20, 25, 30 时给不同的 candidate 投票的情况。
[0, 1, 1, 0, 0, 1, 0]
[0, 5, 10, 15, 20, 25, 30]
但是查询的时刻 t 则分别发生在 3, 12, 25, 15, 24, 8 这几个时刻。
存投票的结果这部分不难，这道题难在如何高效地查询。思路是二分法。存投票这个动作，我们需要一个 hashmap 和一个 list。其中 hashmap 存的是每个 candidate 和他们各自对应的票数。list 里存的是int[] { time, leadingPerson }，意思是在每当有一个人投票之后，我们就看一下当前这次投票结束之后领先的候选人是谁，把这个信息存到 list 里。
因为投票的时刻 time 是有序的，所以 list 里的元素也是按 time 有序的。所以当我们查询的时候就可以用二分法了，这里相当于是在一个有序的数组里找一个最大的小于等于 t 的元素。
复杂度
时间O(logn)
空间O(n)
代码
Java实现
class TopVotedCandidate {
List<int[]> list = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
int max = 0;
public TopVotedCandidate(int[] persons, int[] times) {
int n = persons.length;
for (int i = 0; i < n; i++) {
int person = persons[i];
int time = times[i];
map.put(person, map.getOrDefault(person, 0) + 1);
if (map.get(person) >= max) {
max = map.get(person);
list.add(new int[] {time, person});
}
}
}
public int q(int t) {
int left = 0;
int right = list.size() - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (list.get(mid)[0] == t) {
return list.get(mid)[1];
} else if (list.get(mid)[0] > t) {
right = mid;
} else {
left = mid;
}
}
if (list.get(right)[0] <= t) {
return list.get(right)[1];
}
return list.get(left)[1];
}
}
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* TopVotedCandidate obj = new TopVotedCandidate(persons, times);
* int param_1 = obj.q(t);
*/