tem*_*def 17 language-agnostic random algorithm data-structures
有谁知道有效支持这两个操作的数据结构？
这有点像规范的"弹珠袋",总是出现在介绍概率类中.您可以将任意大理石放入包中,然后可以随意有效地移除大理石.
我有的最佳解决方案如下 - 使用自平衡二叉搜索树(AVL,AA,红/黑等)来存储元素.这给出了O(lg n)插入时间.要删除随机元素,请选择随机索引i,然后在树中找到并删除第i个元素.如果你已经适当地增加了结构,那么也可以在O(lg n)时间内运行.
这个运行时肯定不错,但我很好奇是否有可能做得更好 - 插入可能是O(1)而出列也可能是O(lg n)？或者也许是在预期的 O(1)中使用哈希函数插入和删除的东西？或者可能是一个更强大的摊销限制？
有没有人对如何使这个渐近更快有任何想法？
Chr*_*ung 36
是.使用矢量.
要插入,只需放在最后,然后增加大小.要删除,随机选择一个元素,将其内容与结束值交换,然后弹出结束值(即返回结束值并减小向量的大小).
两个操作均摊销O(1).