相关疑难解决方法(0)

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

1. 将值插入数据结构中.
2. 以统一随机概率从数据结构中出列并返回一个条目.

这有点像规范的"弹珠袋",总是出现在介绍概率类中.您可以将任意大理石放入包中,然后可以随意有效地移除大理石.

我有的最佳解决方案如下 - 使用自平衡二叉搜索树(AVL,AA,红/黑等)来存储元素.这给出了O(lg n)插入时间.要删除随机元素,请选择随机索引i,然后在树中找到并删除第i个元素.如果你已经适当地增加了结构,那么也可以在O(lg n)时间内运行.

这个运行时肯定不错,但我很好奇是否有可能做得更好 - 插入可能是O(1)而出列也可能是O(lg n)？或者也许是在预期的 O(1)中使用哈希函数插入和删除的东西？或者可能是一个更强大的摊销限制？

有没有人对如何使这个渐近更快有任何想法？

在Netwalk游戏中生成迷宫的算法是什么？