在小于O（n）的时间内使用O（1）辅助空间对阵列执行插入，搜索和删除查询

插入（x）插入元素“x”到数组中。
删除（x）从数组中删除元素“x”（假设x存在于数组中）
查找（x）如果数组中存在“x”则返回。

我被允许只使用恒定的辅助空间。

有没有办法在小于O（n）时间内回答这些查询。如果没有，这可以证明吗？即使查询时间稍有改善也是有用的。

您是否熟悉二叉搜索树？ – templatetypedef

@templatetypedef - 是的，但我看不到如何使用恒定的辅助空间来构建它。我知道堆只能使用数组和无指针构建，但我不熟悉在* O（1）*空间中构建平衡二叉搜索树的类似技术。 –

哦，你说得对。你甚至不能用O（1）辅助空间来构建BST。我的错。 – templatetypedef

这是一个实现，它仍然具有用于插入和删除操作的O（n）运行时，但它的运行时间为O（log n）。

将您的数据结构作为一个动态分配的排序数组，没有松弛空间。要执行查找，只需在时间O（log n）中使用二进制搜索。

要做一个插入，分配一个新的n + 1元素数组。复制现有元素，将新元素插入到正确的排序位置。这需要时间O（n）。删除可以类似地实施。

你可以通过选择一些固定的常数k来加快速度，然后每当你需要增长时将数组放入k个元素中。这意味着在k个元素中只有一次需要真正复制数组，所以尽管最坏的运行时仍然是O（n），但插入或删除的摊销成本变为O（n/k）。对于常数k，这与以前渐近一致，但实际上这可能会产生巨大的差异。

希望这会有所帮助！

2015-06-17 16:59:36 templatetypedef

-1

是的，我们可以在O（1）中做数组。插入（x）意味着插入最后它会默认O（1），删除（x）意味着删除索引，并把最后索引删除索引，所以再次它是O（1），搜索内部使用哈希映射，它给你O（1）。

2015-06-17 18:30:27

我不确定我是否理解这个答案。你是什么意思“删除索引？”另外，如何仅使用O（1）辅助存储空间来使用散列表？ – templatetypedef

回答