针对出现过的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