380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象

bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。

bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。

int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

 

示例：

输入

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

[[], [1], [2], [2], [], [1], [2], []]

输出

[null, true, false, true, 2, true, false, 2]

解释

RandomizedSet randomizedSet = new RandomizedSet();

randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。

randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。

randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。

randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。

randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。

randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。

randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

 

我感觉这道题比较难的是搞清楚字典和列表的操作，我一开始就写反了！！

字典是可以取任意位置的，O(1)

列表需要O(1)的话则需要只使用push和pop操作，只操作末尾元素

因此在删除的时候不能直接删除，而是把列表中最后一位放到要删除的位子上，然后删除最后一位~

时间复杂度低了一点，因为random我直接用的random库，没有用choice(）函数

class RandomizedSet:

    def __init__(self):

        self.nums=[]

        self.dict=dict()

    def insert(self, val: int) -> bool:

        if val not in self.dict:

            self.dict[val]=len(self.nums)

            self.nums.append(val)

            return True

        return False

    def remove(self, val: int) -> bool:

        if val in self.dict:

            sw_val=self.nums[-1]

            index=self.dict[val]

            self.nums[index]=sw_val

            self.dict[sw_val]=index

            del self.dict[val]

            self.nums.pop()

            return True

        return False

    #在列表中，只能对nums尾部的元素进行添加或者删除的操作，因此在删除制定位的数字时，需要把最后一个数字放到这个数字的位子上然后删除最后一个数字，此时需要更新字典中的键值对

    def getRandom(self) -> int:

        if len(self.nums)==1:return self.nums[0]

        else:

            ran=random.randint(0,len(self.nums)-1)

            return self.nums[ran]

# Your RandomizedSet object will be instantiated and called as such:

# obj = RandomizedSet()

# param_1 = obj.insert(val)

# param_2 = obj.remove(val)

# param_3 = obj.getRandom()