如何设计一种数据结构，在O(1)时间内完成整数X的查找、插入和删除？

Question

如何设计一种数据结构，在O(1)时间内完成整数X的查找、插入和删除？

algorithmdata-structureslanguage-agnostic

17

这是《算法设计手册》中练习题3-15:

设计一个数据结构，使得插入、删除和查找整数X的时间复杂度均为O(1)（即常数时间，不受存储的整数总数量影响）。假设1≤X≤n且有m + n个空间可用，其中m是任一时刻可以放入表格中的最大整数数量。（提示：使用两个数组A [1..n]和B[1..m]）。您不允许初始化A或B，因为那将需要O(m)或O(n)操作。这意味着数组最初充满了随机垃圾，所以您必须非常小心。

第一句话要求设计一个数据结构，能够在常数时间内完成搜索、插入和删除整数X，而且该数据结构的空间复杂度不能超过m+n。提示使用两个数组A[1..n]和B[1..m]。注意不允许对A或B进行初始化，因为那样会耗费O(m)或O(n)的时间，所以数组A和B最初都充满了随机垃圾。

您的实现方案中只考虑了整数是否存在的情况，但是此练习的要求更加严格，需要能够在常数时间内完成整数的增删改查操作，而且空间限制不能超过m+n。提示中提供了使用两个数组的思路，您需要根据此提示进行思考和设计。

- Jackson Tale

6

启动时无法保证a[5]的值为0。 - andrew cooke

4个回答

3

这里有个想法：将数组B[1..m]视为堆栈，并使指针p指向堆栈的顶部（让p = 0表示没有元素插入到数据结构中）。现在，要插入整数X，请使用以下过程：

p++;
A[X] = p;
B[p] = X;

在这里搜索应该很容易看到（假设X'是您要搜索的整数，那么只需检查1 <= A[X'] <= p，并且B[A[X']] == X'即可）。删除更加棘手，但仍然具有常数时间复杂度。思路是先搜索元素以确认其是否存在，然后将某些东西移动到B中的其位置（一个很好的选择是B[p]），然后更新A以反映替换元素的指针值并弹出栈顶（例如设置B[p] = -1并递减p）。

- Cameron

1

处理重复项的另一种可能性是使用堆栈作为链表。如果B[p]中的数字> = 0，则它包含X，并指向A数组。如果它<0，则指向B[]的前一个元素（再次可以<0或> =）NB：此解决方案比上面的解决方案更好，因为它不需要额外的存储空间（假设负数可以与数字共存，如问题定义所示）。 - wildplasser

我喜欢链表的想法，但问题定义中哪里提到负数可以共存呢？对我来说，“假设 1 ≤ X ≤ n”意味着你可以将所有整数都视为无符号的。 - Cameron

如果有足够的编码空间，您也可以使用index+M。 - wildplasser

1

我第一次看到这个想法是在 Jon Bentley 的《编程珠玑》中 Cameron 的答案里。

这个想法非常简单，但是很难直接看出未初始化数组上可能存在的初始随机值为什么不重要。这链接非常好地解释了插入和搜索操作。删除操作留作练习，但其中一个评论者给出了答案：

remove-member(i):
    if not is-member(i): return
    j = dense[n-1];
    dense[sparse[i]] = j;
    sparse[j] = sparse[i];
    n = n - 1

- kunigami

1

一旦你知道答案，理解问题就会更容易：如果 A[X]<total_integers_stored && B[A[X]]==X，则该整数在集合中。

实际上，这个问题是在问您能否想出如何创建一个可用于最小化初始化的数据结构。

- MSN

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ninjagecko · Accepted Answer

您要做的是基本上实现了一个多重集合，并且有限制的大小，既有元素数量（#elements <= m）又有元素值的有效范围（1 <= elementValue <= n）。

搜索：myCollection.search(x) --> 如果x在集合中则返回True，否则返回False
插入：myCollection.insert(x) --> 将一个x添加到集合中
删除：myCollection.delete(x) --> 从集合中移除一个x

考虑一下，如果您尝试将5存储两次，会发生什么，例如：

myCollection.insert(5)
myCollection.insert(5)

这就是为什么您不能使用位向量。但它说的是“空间单位”，因此您的方法的详细说明是保留每个元素的计数。例如，您可能会有[_,_,_,_,1,_,...]然后是[_,_,_,_,2,_,...]。

然而，这种方法为什么不起作用呢？如果您在未初始化的数组上执行.search(5)会发生什么？您被明确告知不能初始化它，因此您无法确定您将在那片内存中找到的值e.g. 24753是真正意义上的“有 24753 个实例的5”，还是垃圾数据。

注意：您必须允许自己O(1) 的初始化空间，否则问题将无法解决。（否则，.search（）将无法区分内存中的随机垃圾和实际数据，因为您总是可以想出看起来像实际数据的随机垃圾。）例如，您可以考虑使用一个布尔值，表示“我已经开始使用我的内存”，将其初始化为False，并在您开始写入您的m单词内存时将其设置为True。

如果您需要完整的解决方案，可以将鼠标悬停在灰色区域上以显示我想出的方案。它只有几行代码，但证明稍微长一些：

SPOILER: FULL SOLUTION

设置:
使用N个单词作为调度表： locationOfCounts[i] 是大小为N的数组，其值在范围location=[0,M]内。这是存储 i 计数的位置，但我们只能在可以证明它不是垃圾时才能信任此值。 >!
（旁注：这相当于指针数组，但指针数组会暴露出您能够查找垃圾的能力，因此您必须使用具有指针范围检查的代码实现。）

要找出集合中有多少个 i ，您可以从上面查找值为counts[loc]的值。我们使用M个单词作为计数本身： counts 是大小为N的数组，每个元素有两个值。第一个值是它所代表的数字，第二个值是该数字的计数（在范围[1，m]内）。例如，值(5,2)表示集合中存储了2个数字5的实例。
（M 个单词足以容纳所有计数。证明：我们知道永远不会有超过 M 个元素，因此最坏情况是我们拥有 M 个值为 1 的计数。QED）
（我们还选择仅跟踪计数≥1，否则我们将没有足够的内存。）

使用名为numberOfCountsStored的数字进行设置，该数字已初始化为0，但在项目类型更改时进行更新。例如，对于{}，此数字将为0，对于{5:[1 times]}，此数字将为1，对于{5:[2 times]}，此数字将为1，对于{5:[2 times],6:[4 times]}，此数字将为2。

1 2 3 4 5 6 7 8...
locationOfCounts[<N]: [☠, ☠, ☠, ☠, ☠, 0, 1, ☠, ...]
counts[<M]: [(5,⨯2), (6,⨯4), ☠, ☠, ☠, ☠, ☠, ☠, ☠, ☠..., ☠]
numberOfCountsStored: 2

下面我们详细说明每个操作并证明其正确性：

算法:
有两个主要思路：1）我们绝不能允许自己在没有验证它不是垃圾的情况下读取内存，或者如果我们这样做，我们必须能够证明它是垃圾的，2）我们需要能够以O(1)时间证明counter内存