針對出現過的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