難度：★★★☆☆
類型：數(shù)據(jù)結(jié)構(gòu)
方法：二分法
題目
力扣鏈接請(qǐng)移步本題傳送門(mén)
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄
在選舉中灰羽，第 i 張票是在時(shí)間為 times[i] 時(shí)投給 persons[i] 的驮履。
現(xiàn)在鱼辙，我們想要實(shí)現(xiàn)下面的查詢函數(shù)： TopVotedCandidate.q(int t) 將返回在 t 時(shí)刻主導(dǎo)選舉的候選人的編號(hào)。
在 t 時(shí)刻投出的選票也將被計(jì)入我們的查詢之中玫镐。在平局的情況下倒戏，最近獲得投票的候選人將會(huì)獲勝。
示例：
輸入：["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]
解釋：
時(shí)間為 3恐似，票數(shù)分布情況是 [0]杜跷，編號(hào)為 0 的候選人領(lǐng)先。
時(shí)間為 12矫夷，票數(shù)分布情況是 [0,1,1]葛闷，編號(hào)為 1 的候選人領(lǐng)先。
時(shí)間為 25双藕，票數(shù)分布情況是 [0,1,1,0,0,1]孵运，編號(hào)為 1 的候選人領(lǐng)先（因?yàn)樽罱耐镀苯Y(jié)果是平局）。
在時(shí)間 15蔓彩、24 和 8 處繼續(xù)執(zhí)行 3 個(gè)查詢治笨。
提示：
1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times 是嚴(yán)格遞增的數(shù)組，所有元素都在 [0, 10^9] 范圍中赤嚼。
每個(gè)測(cè)試用例最多調(diào)用 10000 次 TopVotedCandidate.q旷赖。
TopVotedCandidate.q(int t) 被調(diào)用時(shí)總是滿足 t >= times[0]。
解答
實(shí)際上只有兩個(gè)問(wèn)題需要考慮：
- 如何記錄各個(gè)標(biāo)志性時(shí)刻下的當(dāng)前獲勝者更卒；
- 如何查詢給定時(shí)刻的獲勝者等孵。
這兩個(gè)問(wèn)題，根據(jù)題目的函數(shù)定義格式蹂空，我們分別寫(xiě)在init函數(shù)和q函數(shù)中俯萌。
定義一個(gè)實(shí)例變量self.winner，這是一個(gè)列表上枕，列表中記錄各個(gè)標(biāo)志時(shí)刻下的當(dāng)前獲勝者咐熙。這里的標(biāo)志時(shí)刻，也就是輸入的times列表辨萍，我們把它也存儲(chǔ)在實(shí)例變量self.times中棋恼，查詢函數(shù)中需要用。
時(shí)刻和當(dāng)前被投票者是成對(duì)出現(xiàn)的锈玉，我們需要準(zhǔn)備一個(gè)計(jì)票器變量votes_of_爪飘，該變量是一個(gè)字典，字典的鍵是各個(gè)候選人拉背，值是各個(gè)候選人的得票师崎。為了便于計(jì)算，我們用python中內(nèi)置的default_dict實(shí)現(xiàn)椅棺，在簡(jiǎn)化表達(dá)的同時(shí)犁罩，省去了找不到鍵的困擾齐蔽。我們還需要準(zhǔn)備中間變量winner_by_now和max_ticket，用以記錄當(dāng)前獲勝的選手及其選票昼汗。
按照時(shí)間順序遍歷各個(gè)投票事件，將當(dāng)前候選人person的選票加一鬼雀，同時(shí)需要及時(shí)的查看這個(gè)候選人是否已經(jīng)達(dá)記錄中曾經(jīng)有過(guò)的最大選票值顷窒，一旦該候選人選票達(dá)到或超過(guò)max_ticket，則說(shuō)明該候選人已經(jīng)成為當(dāng)前時(shí)刻的贏家源哩，需要及時(shí)更新中間變量winner_by_now和max_ticket鞋吉。
在查詢函數(shù)q中，我們使用二分查找法励烦，可以快速定位所查詢的時(shí)間在記錄中出現(xiàn)的位置谓着，由于時(shí)刻列表與各個(gè)時(shí)刻對(duì)應(yīng)的贏家是對(duì)應(yīng)的，找到輸入時(shí)間t對(duì)應(yīng)于時(shí)間列表self.times中的合理位置坛掠，就可以根據(jù)這個(gè)位置快速找到該時(shí)刻對(duì)應(yīng)的贏家赊锚。我們使用bisect可以快速實(shí)現(xiàn)二分法定位操作，注意返回的是插入位置屉栓，需要將該下標(biāo)index-1才能作為當(dāng)前查詢時(shí)刻所在位置舷蒲。
import bisect
from collections import defaultdict
class TopVotedCandidate:
def __init__(self, persons, times):
self.times = times
self.winner = []
votes_of_ = defaultdict(int)
winner_by_now = persons[0]
max_ticket = 0
for person in persons:
votes_of_[person] += 1
if votes_of_[person] >= max_ticket:
winner_by_now = person
max_ticket = votes_of_[person]
self.winner.append(winner_by_now)
def q(self, t):
index = bisect.bisect(self.times, t) - 1
return self.winner[index]
如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案友多，請(qǐng)移步力扣中等題解析
