有谁知道有效支持这两种操作的数据结构?
这有点像标准的“弹珠袋”,它总是出现在入门概率类中。您可以将任意弹珠放入包中,然后可以随机高效地移除弹珠。
我拥有的最佳解决方案如下 - 使用自平衡二叉搜索树(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)。
https://stackoverflow.com/questions/-100008084
复制相似问题