数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++在线选举
假设在一个选举中，第 i 票是在 times[i] 时间投给 persons[i] 的。现在，我们需要实现以下查询函数：TopVotedCandidate.q(int t)，它将查找在时间 t 领先的候选人的编号。在时间 t 投出的选票将计入我们的查询。如果出现平局，则最近的投票（在并列候选人中）获胜。
因此，如果我们用 TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]) 初始化它，然后像这样调用 q()：q(3), q(12), q(25), q(15), q(24), q(8)，那么每次调用 q() 的结果将是 [0, 1, 1, 0, 0, 1]。这是因为在 3 时刻，投票是 [0]，0 领先。在 12 时刻，投票是 [0,1,1]，这里 1 领先。在 25 时刻，投票是 [0,1,1,0,0,1]，1 领先（因为平局取最近的投票）。这将继续进行 3 次更多查询，时间分别为 15、24 和 8。
为了解决这个问题，我们将遵循以下步骤：
创建两个映射 m 和 count
在初始化器中，执行以下任务
lead := -1
对于 i 从 0 到 times 数组的大小
x := times[i]
将 count[persons[i]] 的值增加 1
如果 count[lead] <= count[persons[i]]，则 lead := persons[i] 并且 m[x] := lead；否则 m[x] := lead
q() 方法将如下所示：
在 m 中减小 t 的上限，并返回相应的值
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TopVotedCandidate {
public:
map <int, int> m;
map <int, int> count;
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
int lead = -1;
for(int i = 0; i < times.size(); i++){
int x = times[i];
count[persons[i]]++;
if(count[lead] <= count[persons[i]]){
lead = persons[i];
m[x] = lead;
}else{
m[x] = lead;
}
}
}
int q(int t) {
return ((--m.upper_bound(t)) -> second);
}
};
main(){
vector<int> v1 = {0,1,1,0,0,1,0}, v2 = {0,5,10,15,20,25,30};
TopVotedCandidate ob(v1, v2);
cout << (ob.q(3)) << endl;
cout << (ob.q(12)) << endl;
cout << (ob.q(25)) << endl;
cout << (ob.q(15)) << endl;
cout << (ob.q(24)) << endl;
cout << (ob.q(8)) << endl;
}输入
Initialize the class using [0,1,1,0,0,1,0] and [0,5,10,15,20,25,30]. Call q() method like below: q(3) q(12) q(25) q(15) q(24) q(8)
输出
0 1 1 0 0 1
更新于：2020年4月30日
502 次浏览
广告