要求: each function works in average O(1) time complexity
classRandomizedSet:def__init__(self): self.list = [] self.data_map ={}definsert(self,val:int) ->bool:if val in self.list:returnFalse self.list.append(val) self.data_map[val]=len(self.list)returnTruedefremove(self,val:int) ->bool:if val notin self.data_map:returnFalse last_element = self.list[-1] index_of_element = self.data_map[val] self.data_map[last_element]= index_of_element self.list[index_of_element]= last_element self.list[-1]= val self.list.pop() self.data_map.pop(val)returnTruedefgetRandom(self) ->int:return random.choice(self.list)
时间复杂度:O()
空间复杂度:O()
classRandomizedSet:def__init__(self): self.set =set()definsert(self,val:int) ->bool:if val in self.set:returnFalseelse: self.set.add(val)returnTruedefremove(self,val:int) ->bool:if val in self.set: self.set.remove(val)returnTruereturnFalsedefgetRandom(self) ->int:# set无序,转为list需要创建index,时间复杂度O(n)return random.choice(list(self.set))