Python 中的插入删除 GetRandom O(1)
pythonserver side programmingprogramming更新于 2023/10/8 4:11:00
假设我们有一个数据结构，它支持平均 O(1) 时间内的所有后续操作。
insert(val) − 如果尚不存在项 val，则将项 val 插入到集合中。
remove(val) − 如果存在项 val，则将项 val 从集合中删除。
getRandom − 这将从当前元素集合中返回一个随机元素。每个元素必须具有相同的返回概率。
为了解决这个问题，我们将遵循以下步骤 −
对于初始化，定义一个父映射和元素数组
对于 insert() 函数，它将以 val 作为输入
如果父映射中不存在 val，或者 parent[val] = 0，则将 val 插入元素，并设置 parent[val] := 1，并返回 true
返回 false
对于 remove() 方法，它将使用 val 来删除
如果父映射中不存在 val，或者 parent[val] = 0，则返回 false
设置 parent[val] := 0
index := elements 数组中 val 的索引
如果索引与元素长度不同 – 1
temp := elements 的最后一个元素
设置 elements 的最后一个元素 := val
设置 elements[index] := temp
删除 elements 的最后一个元素
getRandom() 方法将返回 elements 数组中存在的任何随机值
示例 (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
