设计一个支持插入、删除和随机获取元素的数据结构，且时间复杂度均为 O(1)。

Question

Accepted Answer

可以使用一个数组和一个哈希表来实现这个数据结构。数组用于存储元素，哈希表用于记录每个元素在数组中的索引。插入操作：将元素添加到数组的末尾，并在哈希表中记录该元素的索引，时间复杂度为 O(1)。删除操作：先从哈希表中获取要删除元素的索引，将数组末尾的元素移动到该索引位置，并更新哈希表中末尾元素的索引，最后删除数组的最后一个元素和哈希表中要删除元素的记录，时间复杂度为 O(1)。随机获取元素操作：使用随机数生成一个数组的索引，返回该索引对应的元素，时间复杂度为 O(1)。以下是实现代码：
python
import random

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.val_to_index = {}

def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        self.nums.append(val)
        self.val_to_index[val] = len(self.nums) - 1
        return True

def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        index = self.val_to_index[val]
        last_val = self.nums[-1]
        self.nums[index] = last_val
        self.val_to_index[last_val] = index
        self.nums.pop()
        del self.val_to_index[val]
        return True

def getRandom(self) -> int:
        return random.choice(self.nums)

这样就实现了一个支持插入、删除和随机获取元素，且时间复杂度均为 O(1) 的数据结构。