LeetCode题解380.insert-delete-getrandom-o1

题目地址（380. 常数时间插入、删除和获取随机元素）

https://leetcode-cn.com/problems/insert-delete-getrandom-o1/description/

题目描述

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

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

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

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

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

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

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

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

思路

这是一个设计题。这道题的核心就是考察基本数据结构和算法的操作以及复杂度。

我们来回顾一下基础知识：

• 数组支持随机访问，其按照索引查询的时间复杂度为$O(1)$,按值查询的时间复杂度为$O(N)$， 而插入和删除的时间复杂度为$O(N)$。
• 链表不支持随机访问，其查询的时间复杂度为$O(N)$,但是对于插入和删除的复杂度为$O(1)$（不考虑找到选要处理的节点花费的时间）。
• 对于哈希表，正常情况下其查询复杂度平均为$O(1)$，插入和删除的复杂度为$O(1)$。

由于题目要求 getRandom 返回要随机，那么如果单纯使用链表以及哈希表肯定是不行的。而又由于对于插入和删除我们也需要平均复杂度为$O(1)$，因此单纯使用数组也是不行的。我们考虑多种使用数据结构来实现。

实际上 LeetCode 设计题，几乎没有单纯一个数据结构搞定的，基本都需要多种数据结构结合，这个时候需要你对各种数据结构以及其基本算法的复杂度有着清晰的认知。

对于 getRandom 用数组很简单。对于判断是否已经有了存在的元素，我们使用哈希表也很容易做到。因此我们将数组随机访问，以及哈希表$O(1)$按值检索的特性结合起来，即同时使用这两种数据结构。

对于删除和插入，我们需要一些技巧。

对于插入：

• 我们直接往 append，并将其插入哈希表即可。
• 对于删除，我们需要做到 O(1)。删除哈希表很明显可以，但是对于数组，平均时间复杂度为 O(1)。

因此如何应付删除的这种性能开销呢？ 我们知道对于数据删除，我们的时间复杂度来源于

1. 查找到要删除的元素
2. 以及重新排列被删除元素后面的元素。

对于 1，我们可以通过哈希表来实现。 key 是插入的数字，value 是数组对应的索引。删除的时候我们根据 key 反查出索引就可以快速找到。

对于 2，我们可以通过和数组最后一项进行交换的方式来实现，这样就避免了数据移动。同时数组其他项的索引仍然保持不变，非常好！

相应的我们插入的时候，需要维护哈希表

关键点解析

• 数组
• 哈希表
• 数组 + 哈希表
• 基本算法时间复杂度分析

代码

from random import random


class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = dict()
        self.arr = []
        self.n = 0

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.data:
            return False
        self.data[val] = self.n
        self.arr.append(val)
        self.n += 1

        return True

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.data:
            return False
        i = self.data[val]
        # 更新data
        self.data[self.arr[-1]] = i
        self.data.pop(val)
        # 更新arr
        self.arr[i] = self.arr[-1]
        # 删除最后一项
        self.arr.pop()
        self.n -= 1

        return True

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """

        return self.arr[int(random() * self.n)]


# 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()

从实体获取或创建插入语句 - java

是否存在具有值的现有实体类生成插入语句的可能性？编辑：我的意思是为实体类的实例生成一个插入语句，以单独执行该语句。提前致谢 java大神给出的解决方案 使用Fastnate，您可以为没有连接数据库的实体创建SQL语句：public String createSQL() { // Create your entity TestEntity entity = n…

LeetCode题解238.product-of-array-except-self

题目地址 https://leetcode.com/problems/product-of-array-except-self/description/ 题目描述 Given an array nums of n integers where n > 1, return an array output such that output[i] is eq…

在matplotlib动画模块中管理动态绘图 - python

我想要一个迭代绘制的图，该图允许跳到下一帧，停止它并返回到上一帧。我看过matplotlib动画模块，如果有一种方法可以实现以前的帧功能（例如，按下某个键时向后运行动画几帧），则该模块将是完美的像这样的事情会很好：def update_frame(i, data): fig.set_data(data[i]) 但是我可以明确地管理迭代器是增加还是减少。有没有…

LeetCode题解如何用数组实现链表

一般链表的实现不是基于数组的，而是基于指针的。那是否可以用数组模拟呢？如果可以的话，为什么大家都不用呢？ 请大家尝试自己实现之。 题解：不知道和leetcode 707是不是同一个意思，我这实现了707的，等会再看看大佬们的答案。Python版：```pyclass Node: def __init__(self, val): self.val = val …

LeetCode题解225. 用队列实现栈

使用队列实现栈的下列操作：push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空注意:你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可…