LeetCode //380. Insert Delete GetRandom O(1)

**LeetCode380. Insert Delete GetRandom O(1)****概述**

在这个问题中，我们需要实现一个支持随机访问的数据结构，能够插入、删除和获取随机元素。要求是所有操作的时间复杂度为 O(1)。

**解决方案**

我们将使用哈希表来存储元素，并且使用链表来维护元素的顺序。这可以保证在任何时候，我们都能找到一个随机的元素。

###代码实现

import randomclass RandomizedSet:

 def __init__(self):
 """
 Initialize your data structure here.
 """
 self.val_to_index = {} # 值到索引的映射 self.index_to_val = [] # 索引到值的映射 def insert(self, val: int) -> bool:
 """
 Inserts a value to the set. Returns true if the set did not already contain the specified element.
 @param val The value to be inserted.
 @return True if the set did not already contain the specified element or False otherwise.
 """
 # 如果值已经存在，则返回False if val in self.val_to_index:
 return False # 将新值添加到索引列表中 self.index_to_val.append(val)
 # 更新值到索引的映射 self.val_to_index[val] = len(self.index_to_val) -1 return True def remove(self, val: int) -> bool:
 """
 Removes a value from the set. Returns true if the set contained the specified element.
 @param val The value to be removed.
 @return True if the set contained the specified element or False otherwise.
 """
 # 如果值不存在，则返回False if val not in self.val_to_index:
 return False # 获取索引 index = self.val_to_index[val]
 # 将最后一个元素的值复制到当前位置 last_val = self.index_to_val[-1]
 self.index_to_val[index] = last_val # 更新值到索引的映射 self.val_to_index[last_val] = index # 删除最后一个元素 del self.index_to_val[-1]
 # 删除值到索引的映射 del self.val_to_index[val]
 return True def getRandom(self) -> int:
 """
 Get a random element from the set.
 @return A random element from current set of elements. If the set is empty, returns0.
 """
 # 如果索引列表为空，则返回0 if not self.index_to_val:
 return0 # 随机选择一个索引 index = random.randint(0, len(self.index_to_val) -1)
 # 返回对应的值 return self.index_to_val[index]

randomizedSet = RandomizedSet()
print(randomizedSet.insert(1)) # Trueprint(randomizedSet.remove(2)) # Falseprint(randomizedSet.insert(2)) # Trueprint(randomizedSet.getRandom()) #2print(randomizedSet.remove(1)) # Trueprint(randomizedSet.getRandom()) #2