使用getRandom设置

Question

这是一个面试问题:Impement一个Set带班get,put和getRandom.

我会考虑以下选项:

• 排序/未排序的链表:get- O(N),put- O(N),getRandom- O(N)
• 未排序的向量(可调整大小的数组):get- O(N),put- ？,getRandom- O(1)
• 排序向量(可调整大小的数组):get- O(logN),put- ？,getRandom- O(1)
• 哈希表:get- O(1),put- O(1),getRandom- O(表大小)
• 平衡二叉搜索树:get- O(logN),put- O(logN),getRandom- O(N)

看起来最好的候选人是:

• 哈希表如果get/put频繁得多getRandom
• 排序的矢量(可调整大小的数组),如果getRandom比它更频繁get/put

现在我想知道我们是否可以以某种方式组合向量和散列表来构成更好的集合.

Answer 1

你可以做get,put而且getRandom都是O(1)平均时间.

你要做的是存储2个数据结构.一个是哈希.另一个在可增长数组中以随机顺序列出元素.

当你put把它放在哈希中时,将元素添加到数组的末尾,然后将数组的末尾交换为随机数组元素.

当你get,你在哈希中查找元素.

当你getRandom,你获取数组的最后一个元素,然后将最后一个元素与数组中的另一个点交换.

如果您愿意,可以添加delete为删除哈希.现在getRandom通过获取元素来实现,检查它是否在散列中,如果不是,则缩小数组,然后重复.在这一点上getRandom是偶然O(n) 但所有操作的平均摊销成本可以证明O(1).