algorithm - 采访: Suggest a data structure which optimizes insertion,删除和随机值生成

Question

建议一个可以优化以下所有 3 个操作的数据结构:

1. 插入
2. 删除
3. 从一组现有值中返回一个随机值

假设您要输入整数/数字。

Answer 1

对于所有三个操作，动态数组 + Hashmap = O(1)

• 插入

附加到数组 O(1) 的尾部，并将值索引对添加到 Hashmap O(1)。

• 删除

通过Hashmap O(1)中的值找到索引，通过数组中的索引删除并将最后一个元素交换到槽O(1)中，并更新值-索引对(used-to-be ) 最后一个元素 O(1)。

• 随机返回

为 O(1) 的数组生成一个随机索引。