→ DJYOMIYAHINA: 我居然是今天第一篇 你們就繼續板聚沒關係 02/08 20:28
推 oin1104: 對不起 02/08 20:28
推 JIWP: 別捲了 02/08 20:29
針對出現過的number都maintain一個minheap
change的時候 只管把index push到對應的minheap
不去管被替代掉的數字的heap
只是find的時候
要去確認pop出的index位置 是不是真的是那個number
若否 則繼續pop到是為止
若heap空了就回傳-1
我也不知道為啥會想到這種方法
def __init__(self):
self.mp = defaultdict(list)
self.arr = {}
def change(self, index, number):
"""
:type index: int
:type number: int
:rtype: None
"""
heappush(self.mp[number], index)
self.arr[index] = number
return
def find(self, number):
"""
:type number: int
:rtype: int
"""
while len(self.mp[number]) != 0:
cur_idx = self.mp[number][0]
if cur_idx in self.arr and self.arr[cur_idx]==number:
return cur_idx
else:
heappop(self.mp[number])
return -1
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1739017657.A.920.html