algorithm - 为 O(1) 中的基本操作设计一个范围为 1 到 1000（不重复）的整数的数据结构

Question

为以下操作设计一个范围为 1 到 1000（不重复）的整数的数据结构。 1）插入

2）删除

3)搜索

4)int Anyvalid() -> 这应该返回当时存在的任何有效/当前数字。 例如，如果存在 1、5、7，则返回 3 个数字中的任何一个。

所有操作都应该是 0(1)/常数时间。

我想到了位向量，但在 AnyvalidElement() 的情况下它给出 0(n) .. 其余的它在 0(1) 中工作。

Answer 1

Use a doubly linked list and an array of pointers to the list nodes.

• Insert n: Add n to the front of the list, array[n] = pointer to newly added node.
• Delete n: Use array to jump to the correct node in the list and remove it. Set array[n] = NULL;
• Search n: check if array[n] != NULL
• AnyValid: return front of the list