网站模糊背景,杭州建设企业网站,管理咨询公司企业文化,制作网站程序文章目录1. 题目2. 解题1. 题目
在选举中#xff0c;第 i 张票是在时间为 times[i] 时投给 persons[i] 的。
现在#xff0c;我们想要实现下面的查询函数#xff1a; TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。
在 t 时刻投出的选票也将被计入…
文章目录1. 题目2. 解题1. 题目
在选举中第 i 张票是在时间为 times[i] 时投给 persons[i] 的。
现在我们想要实现下面的查询函数 TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。
在 t 时刻投出的选票也将被计入我们的查询之中。 在平局的情况下最近获得投票的候选人将会获胜。
示例
输入[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]]
输出[null,0,1,1,0,0,1]
解释
时间为 3票数分布情况是 [0]编号为 0 的候选人领先。
时间为 12票数分布情况是 [0,1,1]编号为 1 的候选人领先。
时间为 25票数分布情况是 [0,1,1,0,0,1]编号为 1 的候选人领先因为最近的投票结果是平局。
在时间 15、24 和 8 处继续执行 3 个查询。提示
1 persons.length times.length 5000
0 persons[i] persons.length
times 是严格递增的数组所有元素都在 [0, 10^9] 范围中。
每个测试用例最多调用 10000 次 TopVotedCandidate.q。
TopVotedCandidate.q(int t) 被调用时总是满足 t times[0]。来源力扣LeetCode 链接https://leetcode-cn.com/problems/online-election 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
记录最大选票数量获胜者按时间顺序记录下获胜者然后二分查找小于等于 t 时刻的最后一个时间点读取该时刻的获胜者
class TopVotedCandidate {vectorint winner;vectorint T;
public:TopVotedCandidate(vectorint persons, vectorint times) {int maxVotes 0, winId -1;unordered_mapint,int votes;//人得票数T times;for(int i 0; i persons.size(); i) {votes[persons[i]];if(votes[persons[i]] maxVotes){winId persons[i];maxVotes votes[persons[i]];}winner.push_back(winId);}}int q(int t) {int l 0, r T.size()-1, mid;while(l r)//找小于等于我的最后一个时刻{mid l ((r-l)1);if(T[mid] t)r mid-1;else{if(mid T.size()-1 || T[mid1] t)return winner[mid];elsel mid1;}}return -1;}
};532 ms 91.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
