在常数时间内是否可能在集合中找到一个随机元素？

Question

6

我遇到了一个问题：构建一个带有getRandomElement()函数的集合。乍一看很简单，但是越想越觉得不可能在O(1)时间复杂度内完成。虽然没有给出恒定时间的要求，但是所有集合主要功能都在常数时间范围内，所以我觉得这也应该在常数时间内完成。

集合的目标是通过哈希函数减少碰撞。现在的问题是，如果你简单地生成随机整数并尝试使用此随机整数选择索引，则最有可能在集合中遇到“空”槽......这种情况下，您必须生成新的随机数并重试。实际上，哈希函数越好，使用这种方法的getRandomElement表现越差。

那么我想...好吧，为什么不在每次插入后存储索引呢？然后，从这些索引中生成一个随机数并选择一个索引。我认为这是个好主意，但是接下来就出现了删除元素的问题。我们还必须从索引列表中删除相应的索引，并从集合中删除元素本身。我们如何更快地找到正确的索引以线性时间之外的时间删除？

总之，从集合中获取随机元素感觉可以在线性时间之外完成。顺便说一下，我正在使用链接解决碰撞问题。我不想浪费时间尝试做数学上不可能的事情，但我也不是数学家，我不想放弃实际上可能实现的东西。

- Elroy Jetson

你的问题还不是很清楚。使用 getRandomElement() 函数构建一个集合具体意味着什么？请展示一些（伪）代码并解释它的行为为何不令人满意。 - n. m.

1

我并不一定有问题。我的问题本质上是：是否可以更快地获得随机元素，而不是线性时间。我并不需要代码或编码解决方案来解决问题。 - Elroy Jetson

你想随机获取给定集合中的一个元素，而不是从任何内容构建一个集合。这个措辞正确吗？ - n. m.

所以我们可以按照自己的想法构建这个集合。它必须支持集合的基本功能，但还需要具有一个getRandomElement函数。理论上，您应该能够插入、删除等操作。getRandomElement应该从先前插入的集合中返回一个随机元素。 - Elroy Jetson

2

哦，你想构建一个支持集合操作并且比线性时间更快地执行getRandomElement操作的数据结构，是吗？ - n. m.

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n. m. · Accepted Answer

是的，可以构建一个类似集合的数据结构，支持O(1)的getRandomElement操作。您对将元素存储在数组中的想法是正确的。删除元素的问题并不太困难。秘诀是一旦空洞的数量太大（比如超过数组大小的一半），就压缩数组。这样摊销后的删除时间仍然是O(1)。

执行getRandomElement()时，只需重复直到找到实际的元素。平均重复次数不超过2次，因为数组始终至少半满，所以平均时间复杂度仍为O(1)。

编辑：也许更简单的删除元素方法是将最后一个元素移动到空出的位置。