algorithm - 支持 O(1) remove/insert/findOldest 的数据结构？

Question

面试时问了这个问题:

提出并实现一种数据结构，该数据结构可处理来自最终和连续整数范围的整数数据。数据结构应支持 O(1) 插入和删除操作以及 findOldest(插入到数据结构中的最旧值)。

不允许重复(即如果某个值已经在里面 - 它不应该再添加一次)

此外，如果需要，可以使用 some init 进行初始化。

我提出了一个解决方案，使用 1/0 的数组(大小为范围大小)表示值在里面。它解决了插入/删除并需要O(range size) 初始化。

但我不知道如何使用给定的约束来实现 findOldest。

有什么想法吗？

附言不允许动态分配。

Answer 1

如果我误解了你的问题，我深表歉意，但我的感觉是

• 您有一个正在考虑的固定值范围(例如，[0, N))
• 您需要支持不重复的插入和删除。
• 您需要支持 findOldest。

一个选项是构建一个长度为 N 的数组，其中每个条目都存储一个 bool 值“处于事件状态”标志以及一个指针。此外，每个条目中都有一个双向链表单元格。直觉上，您正在构建一个带有链表的位向量，链表通过它存储插入顺序。

最初，所有位都设置为 false，指针全部为 NULL。当您进行插入时，将相应单元格上的位设置为 true(如果已设置则立即返回)，然后通过将此新单元格附加到它来更新元素的双向链接列表。这需要时间 O(1)。要执行 findOldest 步骤，只需查询指向最旧元素的指针。最后，要执行删除步骤，清除相关元素上的位并将其从双向链表中删除，必要时更新头指针和尾指针。

总而言之，所有操作都需要时间 O(1)，并且没有执行动态分配，因为链表单元格是作为数组的一部分预先分配的。

希望这对您有所帮助!