algorithm - 用 getRandom 设置

Question

这是一道面试题:使用get、put 和getRandom 实现一个Set 类。

我会考虑以下选项:

• 排序/未排序链表: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 时，您将其放入散列中，将元素添加到数组的末尾，然后将数组的末尾交换为随机数组元素。

当您获取时，您会在散列中查找该元素。

getRandom 时，您获取数组的最后一个元素，然后将最后一个元素与数组中的另一个位置交换。

如果您愿意，您可以添加delete 只是删除散列。现在 getRandom 是通过获取元素来实现的，检查它是否在散列中，如果不在，则收缩数组，然后重复。此时getRandom偶尔是O(n) 但是所有操作的摊销平均成本可以证明是O(1 )。