问用于选择随机元素的数据结构？
EN

Stack Overflow用户

提问于 2018-04-12 06:51:28

回答 1查看 0关注 0票数 0

有谁知道有效支持这两种操作的数据结构？

这有点像标准的“弹珠袋”，它总是出现在入门概率类中。您可以将任意弹珠放入包中，然后可以随机高效地移除弹珠。

我拥有的最佳解决方案如下 - 使用自平衡二叉搜索树（AVL，AA，红/黑等）来存储元素。这会给O（lg n）插入时间。要移除一个随机元素，选择一个随机索引i，然后从树中找到并移除第i个元素。如果你已经适当地扩大了结构，那么也可以在O（lg n）时间内运行。

这个运行时肯定不坏，但我很好奇，如果有可能做得更好 - 也许O（1）用于插入，O（lg n）用于出队？或者可能是在预期的 O（1）中使用散列函数插入和删除的东西？或者也许是一个更强大的摊销边界？

有没有人有任何想法如何让这渐近更快？

发布于 2018-04-12 16:27:31

是。使用矢量。

要插入，只需放在最后，然后增加大小。要移除，随机选取一个元素，将其内容与最终值交换，然后弹出结束值（即返回结束值并减小向量的大小）。

两项业务均摊销O（1）。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/-100008084

复制

相似问题

问用于选择随机元素的数据结构？EN