use*_*er7 2 language-agnostic complexity-theory big-o data-structures
面试问题:
提出一个数据结构,它保存从0到n - 1的元素,并支持O(1)时间内的所有以下操作:初始化,元素插入,元素删除,查找元素,删除所有元素.
哈希表(假设没有冲突,即最好的情况)将支持在O(1)中插入和搜索.我不确定删除虽然......任何想法？
非常有趣的问题!
假设内存分配和事务处理是O(1),那么所有的O(1)都是可能的.
为此我们使用Hopcroft和Ullman的技巧,它允许我们使用大小为n的数组,而不必花费Omega(n)时间来实际初始化它们.
见这里:http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/
在插入时,我们只使用上面的数组并将其设置为1.在搜索中,如果我们发现数组元素未初始化,则返回0.在删除时,我们将其设置为0.
在全部删除时,我们释放数据结构并使用新数据结构.