用散列表摊销时间

Question

我解决了问题的第一部分，但仍停留在第二部分。

我有一部电梯，想要支持以下几点：

Init()将电梯设置为从0层开始，其行程方向向上(此函数只被调用一次，方向不能更改)。O(1)

AddStop(K)保存到DS中，当电梯到达楼层k. O(log )时，电梯应该停止，而n是电梯的总停止数。

NextStop()将电梯发送到其下一站位置，如果它位于最终可用的停站位置，那么电梯将停留在其当前位置。O(1)。

我的解决方案:我使用了AVL树，这样每个节点都有一个指向它后面的节点和它前面的节点的指针(根据楼层编号)。

当我添加新的楼层时，我相应地更改它的2个指针，并将指针更改到树中的受影响节点。

第2部分：

大家都知道，在我叫了AddStop(K)之后，电梯能停的最高楼层是最大的2i。

新的复杂时间要求：

Init() - O(1).(没有改变)

AddStop(K) - O(1).用NextStop()摊销

NextStop() - O(1).用AddStop(K)摊销

有人能帮我解决第二部分吗？

更新：

我认为第1部分与解决第2部分无关，Plus I强烈认为我们应该在这里使用Hash表。

Answer 1

重要的是这个条件：

，在我叫AddStop(K)之后，电梯能停的最高楼层是最大2i。

这意味着，在最坏的情况下，你会停在一半的楼层，所以让一个数组按楼层编号进行索引，存储一个布尔值来表示是否停止，并不是很浪费。

对于NextStop()，只需从当前的楼层位置迭代，直到找到要停的下一层。

为了使复杂度保持在摊销的O(1)，每当AddStop需要一个更大的数组时，就足以调整数组的大小，使其以前的大小翻一番。这样的话，假设你最后有一个X层，0到一半的地板会在上次调整后直接加进去，一半到1/4必须在你调整尺寸的时候复制一次，1/4到1/8将被复制两次，1/8到1/16复制三次等等--最坏的情况是，拷贝的数量是1+ 2/2 + 3/4 +4/4+ 4/8 + 5/16等等。Nicole Oresme定理说，水平在4--一个常数因子O(1)仍在摊销。

不涉及哈希表。