在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