问题陈述
假设我们有一个无限数组,我们在其中存储整数。当数组中有 n
个元素时,只有 n
个单元格被使用,其余为空。
我正在尝试提出一种数据结构/算法,它能够:
- 检查元素是否被存储
- 如果尚未存储则插入一个新元素
- 删除存储的元素
每个操作都必须在 O(sqrt(n))
中。
方法一
我遇到了 this site ,其中提出了以下算法:
- 数组(实际上,想象一下)分成子数组。它们的长度为 1、4、9、16、25、36、49 等。最后一个子数组不是一个完美的正方形 - 它可能没有完全填满。
- 假设,当我们将这些子数组视为集合时 - 它们按递增顺序排列。因此,更靠右的堆中的所有元素都大于其左侧堆中的任何元素。
- 每个这样的子数组代表一个二叉堆。最大堆。
- 查找:转到堆的第一个索引(又是 1、4、9、16,...),只要找到第一个堆的最大值(最大值存储在这些索引中)大于你的号码。然后检查这个子数组/堆。
- 插入:完成查找后,将元素插入堆中应有的位置。当堆满时 - 取出最大的元素并将其插入下一个堆。等等。
不幸的是,这个解决方案是O(sqrt(n) * log(n))
。
如何让它成为纯粹的O(sqrt(n))
?
想法2
由于所有操作都需要执行查找,我想插入和删除都是 O(1)
。只是一个猜测。并且可能一旦插入完成,删除将是显而易见的。
澄清
What does the infinite array mean?
基本上,您可以在其中存储任意数量的元素。它是无限的。但是,有两个限制。第一 - 一个单元格只能存储一个元素。其次 - 当数组存储当前 n 个元素时,只能使用前 n 个单元格。
What about the order?
没关系。
最佳答案
您是否考虑过 bi-parental heap (又名:BEAP)?
堆保持sqrt(n)
的高度,也就是说insert,find,remove都运行在O(sqrt(n))
的最坏情况下案例。
Munro 和 Suwanda 1980 年的论文 Implicit data structures for fast search and update 中描述了这些结构.
关于arrays - 如何设计插入到无限数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37292186/