Insert Delete GetRandom O(1) (Leetcode 380)
Problem Link: https://leetcode.com/problems/insert-delete-getrandom-o1/
class RandomizedSet:
def __init__(self):
self.d={}
self.nums=[]
def insert(self, val: int) -> bool:
if(val in self.d):
return False
else:
self.d[val]=len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if(val not in self.d):
return False
else:
idx=self.d[val]
lastele=self.nums[-1]
self.nums[idx]=lastele
# Do not write del self.d[val] in this line
# write it at the end.
# To understand more, try a testcase where
# there is only one element
# Try this test case:
# ["RandomizedSet","remove","remove","insert","getRandom","remove","insert"]
# [[],[0],[0],[0],[],[0],[0]]
self.nums.pop()
self.d[lastele]=idx
del self.d[val]
return True
def getRandom(self) -> int:
return random.choice(self.nums)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
Last updated