是否有可能在SetinConstant时间内找到一个随机元素？

因此,我遇到了使用getRandomElement()函数构建集合的问题.乍一看很容易.但是我想的越多,我认为在O(1)时间复杂度中做到这一点的可能性越小.没有给出恒定时间的要求,但所有一组主要功能都是在恒定的时间内,所以我觉得它暗示这也应该在恒定时间内完成.

集合的目标是使用散列函数来减少冲突.问题现在变成,如果你只是生成随机整数并尝试使用这个随机整数选择索引,你很可能会遇到你的集合中的"空"插槽....在这种情况下你必须生成一个新的随机数然后再试一次.基本上你的散列函数越好,你的getRandomElement将使用这种方法执行的最差.

那么我想......好吧,为什么不在每次插入后存储索引？然后,生成一个随机数并从该索引集合中选择一个索引.我认为这是一个好主意,但后来出现了删除元素的问题.我们还必须从索引列表中删除相应的索引,以及从我们的Set中删除元素本身.我们怎样才能找到正确的索引来删除比线性时间更快的???

无论如何,从一组FEELS中获取一个随机元素就可以比线性时间更好.顺便说一下,我正在通过链接来处理碰撞.我不想浪费时间去做数学上不可能的事情,但我也不是数学家,我不想放弃实际可行的事情.

是的,可以构建一个支持O(1)getRandomElement操作的类似集合的数据结构.您是否正确地将元素存储在数组中.去除元素的问题并不太难.

秘密是一旦孔的数量太大(例如,超过阵列大小的一半)就压缩阵列.这样,摊销的删除时间仍为O(1).

执行时getRandomElement(),只需重复操作直到遇到实际元素.平均重复次数不超过2,因为数组总是至少半满,所以你的平均时间仍为O(1)getRandomElement().

编辑:或许删除元素的简单方法是将最后一个元素移动到空出的位置.