支持O(1)删除/插入/查找的数据结构？
支持O(1)删除/插入/查找的数据结构？
提问于 2013-11-05 21:19:04
这一问题是在采访中提出的：
提出并实现一种数据结构，该结构与整数的最终和连续范围内的整数数据一起工作。数据结构应该支持O(1)插入和删除操作以及findOldest (插入到数据结构的最古老的值)。
不允许重复(即，如果已经存在某种价值-不应再添加一次)
另外，如果需要，可以使用一些init进行初始化。
我提出了一种解决方案，使用1/0的数组(大小作为范围大小)，指示值在内部。它解决了插入/删除，并需要O(range size)初始化。
但是我不知道如何在给定的约束条件下实现findOldest。
有什么想法吗？
不允许动态分配。
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-11-05 21:44:35
如果我误解了你的问题，我很抱歉，但我明白
- 您正在考虑的值范围是固定的(例如，[0，N])
- 您需要支持没有重复的插入和删除。
- 您需要支持findOldest。
一个选项是构建一个长度为N的数组，其中每个条目存储一个布尔值“是活动的”标志以及一个指针。此外，每个条目都有一个双链接列表单元格。直观地说，您正在构建一个位向量，其中有一个链表，通过它来存储插入顺序。
最初，所有位都设置为false，指针都为NULL。在进行插入时，将适当单元格上的位设置为true (如果已经设置，则立即返回)，然后将这个新单元格追加到元素的双链接列表中。这需要时间O(1)。要执行findOldest步骤，只需查询指向最老元素的指针。最后，要执行删除步骤，请清除该元素上的位，并将其从双链接列表中删除，必要时更新头指针和尾指针。
总之，所有操作都需要时间O(1)，不执行动态分配，因为链接列表单元是作为数组的一部分预先分配的。
希望这能有所帮助！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19799185
复制相关文章
相似问题
腾讯云开发者
