在Python中插入Delete GetRandom O(1)
假设我们有一个数据结构在平均O(1)时间内支持所有以下操作。
insert(val)-这将在集合中插入项目val（如果尚不存在）。
remove(val)-如果存在，它将从集合中移除项目val。
getRandom-这将从当前元素集合中返回一个随机元素。每个元素必须具有相同的返回概率。
为了解决这个问题，我们将遵循以下步骤-
对于初始化，定义父映射和elements数组
对于该insert()函数，它将以val作为输入
如果父映射中不存在val，或者parent[val]=0，则将val插入元素，并设置parent[val]：=1，然后返回true
返回假
对于该remove()方法，将需要val才能删除
如果父映射中不存在val，或者parent[val]=0，则返回false
设置parent[val]：=0
index：=元素数组中val的索引
如果索引与元素长度不同–1
temp：=元素的最后一个元素
设置元素的最后一个元素：=val
设置元素[索引]：=临时
删除元素的最后一个元素
该getRandom()方法将返回元素数组中存在的任何随机值
示例(Python)
让我们看下面的实现以更好地理解-
import random
class RandomizedSet(object):
def __init__(self):
self.present = {}
self.elements = []
def insert(self, val):
if val not in self.present or self.present[val] == 0:
self.elements.append(val)
self.present[val] = 1
return True
return False
def remove(self, val):
if val not in self.present or self.present[val] == 0:
return False
self.present[val] = 0
index = self.elements.index(val)
if index!=len(self.elements)-1:
temp = self.elements[-1]
self.elements[-1] = val
self.elements[index]=temp
self.elements.pop()
return True
def getRandom(self):
return random.choice(self.elements)
ob = RandomizedSet()print(ob.insert(1))
print(ob.remove(2))
print(ob.insert(2))
print(ob.getRandom())
print(ob.remove(1))
print(ob.insert(2))
print(ob.getRandom())输入项
Initialize the class, then call the insert(), remove(), getRandom() functions. See the implementation.
输出结果
True False True 2 True False 2