資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告