这是一个面试问题：弹劾一个有Set，get和put的班级。
我将考虑以下选择：
排序/未排序链表：getRandom-o（n），get-o（n），put-o（n）
未排序向量（可调整大小的数组）：getRandom-o（n），get-？，put-o（1）
排序向量（可调整大小的数组）：getRandom-o（logn），get-？，put-O（1）
哈希表：getRandom-O（1），get-O（1），put-O（表大小）
平衡二叉搜索树：getRandom-o（logn），get-o（logn），put-o（n）
看起来最好的候选人是：
hash table ifgetRandom比get/put更频繁
如果getRandom比getRandom更频繁，则排序向量（可调整大小的数组）
现在我想知道我们是否可以组合一个向量和散列表来组成一个更好的集合。
最佳答案
您可以将get、put和getRandom都设为O(1)平均时间。
您要做的是存储2个数据结构。一个是杂凑。另一个以随机顺序列出可增长数组中的元素。
当put时，将其放入哈希中，将元素添加到数组的末尾，然后将数组的结尾替换为随机数组元素。
当您get时，您将在散列中查找元素。
当getRandom时，获取数组的最后一个元素，然后将最后一个元素与数组中的另一个点交换。
如果需要，可以添加delete作为删除散列现在getRandom是通过获取元素、检查它是否在散列中、如果不在散列中，则收缩数组并重复来实现的。此时getRandom偶尔会O(n)但所有业务的摊余平均成本可以证明O(1)。