PythonでDeleteGetRandomO（1）を挿入します

• insert（val）-これは、アイテムvalがまだ存在しない場合、セットに挿入します。

• remove（val）-これにより、アイテムvalが存在する場合、セットから削除されます。

• getRandom-これは、現在の要素のセットからランダムな要素を返します。各要素は、返される確率が同じである必要があります。

これを解決するには、次の手順に従います-

• 初期化には、親マップと要素配列を定義します

• insert（）関数の場合、入力としてvalを取ります

  • valが親マップに存在しない場合、またはparent [val] =0の場合、要素にvalを挿入し、parent [val]：=1を設定して、trueを返します

• falseを返す

• remove（）メソッドの場合、削除するにはvalが必要です

• valが親マップに存在しない場合、またはparent [val] =0の場合、falseを返します

• 親を設定[val]：=0

• index：=要素配列のvalのインデックス

• インデックスが要素の長さと同じでない場合– 1

  • temp：=要素の最後の要素

  • 要素の最後の要素を設定します：=val

  • set elements [index]：=temp

• 要素の最後の要素を削除する

• 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