380 Insert Delete GetRandom O(1)
380. Insert Delete GetRandom O(1)
题目： https://leetcode.com/problems/insert-delete-getrandom-o1/
难度 : Hard
我的naive TLE代码，关键还是在想这个getRandom,这就不是O(1)的：
class RandomizedSet(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.container = {}
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
# 1 stands for present
if val in self.container and self.container[val] == 1:
return False
else:
self.container[val] = 1
return True
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if self.container.get(val,0) == 1:
self.container[val] = 0
return True
else:
return False
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
import random
keys = self.container.keys()
rd = random.randint(0, len(keys) - 1)
if self.container[keys[rd]] == 1:
return keys[rd]
elif self.container.get(keys[rd],0) == 0:
return self.getRandom()
Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.
1.insert(value): append the value to array and let i be its index in A. Set H[value]=i.
2.remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
3.contains(value): return H.contains(value)
4.getRandomElement(): let r=random(current size of A). return A[r].
since the array needs to auto-increase in size, it's going to be amortize O(1) to add an element, but I guess that's OK.
按照以答案AC代码
class RandomizedSet(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.hashtable = {}
self.array = []
self.arraySize = 0
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
# already in the set
if val in self.hashtable:
return False
else:
self.hashtable[val] = self.arraySize
self.array.append(val)
self.arraySize += 1
return True
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val not in self.hashtable:
return False
else:
removeIdx = self.hashtable[val]
if self.arraySize == 1:
self.__init__()
else:
self.array[removeIdx] = self.array[-1]
self.hashtable[self.array[-1]] = removeIdx
self.arraySize -= 1
del self.hashtable[val]
del self.array[-1]
return True
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
import random
rd = random.randint(0, self.arraySize-1)
return self.array[rd]
最后getRandom也可以写成：
return random.choice(self.array)
