[LeetCode] 911. Online Election
grandyang opened this issue · 0 comments
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 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times
is a strictly increasing array with all elements in[0, 10^9]
.TopVotedCandidate.q
is called at most10000
times per test case.TopVotedCandidate.q(int t)
is always called witht >= times[0]
.
这道题是关于线上选举的问题,这年头感觉选举都是得网络者得天下啊,很多都是先在网上形成了一股潮流,比如美国的特朗普,英国的约翰逊,**的韩国瑜等等,感觉各个都是社交媒体上的红人,不走寻常路啊。扯远了,拉回本题,其实刚开始博主看了几遍题目,愣是没理解题意,于是去论坛上逛逛,发现也有好多人不清楚,心里稍微舒坦点。这里给了两个数组 persons 和 times,表示在某个时间点 times[i],i这个人把选票投给了 persons[i],现在有一个q函数,输入时间点t,让返回在时间点t时得票最多的人,当得票数相等时,返回最近得票的人。因为查询需求的时间点是任意的,在某个查询时间点可能并没有投票发生,但需要知道当前的票王,当然最傻的办法就是每次都从开头统计到当前时间点,找出票王,但这种方法大概率会超时,正确的方法实际上是要在某个投票的时间点,都统计出当前的票王,然后在查询的时候,查找刚好大于查询时间点的下一个投票时间点,返回前一个时间点的票王即可,所以这里可以使用一个 TreeMap 来建立投票时间点和当前票王之间的映射。如何统计每个投票时间点的票王呢,可以使用一个 count 数组,其中 count[i] 就表示当前i获得的票数,还需要一个变量 lead,表示当前的票王。现在就可以开始遍历所有的投票了,对于每个投票,将票数加到 count 中对应的人身上,然后跟 lead 比较,若当前人的票数大于等于 lead 的票数,则 lead 更换为当前人,同时建立当前时间点和票王之间的映射。在查询的时候,由于时间点是有序的,所以可以使用二分搜索法,由于使用的是 TreeMap,具有自动排序的功能,可以直接用 upper_bound 来查找第一个比t大的投票时间,然后再返回上一个投票时间点的票王即可,参见代码如下:
解法一:
class TopVotedCandidate {
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
int n = persons.size(), lead = 0;
vector<int> count(n + 1);
for (int i = 0; i < n; ++i) {
if (++count[persons[i]] >= count[lead]) {
lead = persons[i];
}
m[times[i]] = lead;
}
}
int q(int t) {
return (--m.upper_bound(t))->second;
}
private:
map<int, int> m;
};
我们也可以用 HashMap 来取代 TreeMap,但因为 HashMap 无法进行时间点的排序,不好使用二分搜索法了,所以就需要记录投票时间数组 times,保存在一个私有变量中。在查询函数中自己来写二分搜索法,是博主之前的总结帖 LeetCode Binary Search Summary 二分搜索法小结 中的第三类,查找第一个大于目标值的数。由于要返回上一个投票时间点,所以要记得减1,参见代码如下:
解法二:
class TopVotedCandidate {
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
int n = persons.size(), lead = 0;
vector<int> count(n + 1);
this->times = times;
for (int i = 0; i < n; ++i) {
if (++count[persons[i]] >= count[lead]) {
lead = persons[i];
}
m[times[i]] = lead;
}
}
int q(int t) {
int left = 0, right = times.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (times[mid] <= t) left = mid + 1;
else right = mid;
}
return m[times[right - 1]];
}
private:
unordered_map<int, int> m;
vector<int> times;
};
Github 同步地址:
参考资料: