访谈:建议一种优化插入,删除和随机值生成的数据结构

Question

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

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

假设您输入整数/数字.

Answer 1

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

• 插入

附加到Array O(1)的尾部,并将值索引对添加到Hashmap O(1).

• 删除

通过Hashmap O(1)中的值查找索引,通过数组中的索引删除并将最后一个元素交换到插槽O(1)中,并更新(以前用过的)最后一个元素的value-index对O(1).

• 随机返回

为数组O(1)生成随机索引.