[LeetCode] 911. Online Election

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);
 */