algorithm - 如何设计一种允许在O(1)时间内搜索，插入和删除整数X的数据结构

Question

这是“算法设计手册”一书中的练习（3-15）。


设计一种数据结构，该结构允许人们在O（1）时间（即恒定时间，与存储的整数总数无关）中搜索，插入和删除整数X。假定1≤X≤n，并且有m + n个可用的空间单位，其中m是任何时候表中可以存在的最大整数数。 （提示：使用两个数组A [1..n]和B [1..m]。）不允许初始化A或B，因为那样会进行O（m）或O（n）运算。这意味着数组从一开始就充满了随机垃圾，因此您必须非常小心。


我并不是真正在寻找答案，因为我什至不了解该练习的要求。

从第一句话开始：


设计一种数据结构，该结构允许在O（1）时间内搜索，插入和删除整数X


我可以轻松地设计出这样的数据结构。例如：

因为1 <= X <= n，所以我只有一个n个插槽的位向量，并且让X为数组的索引，例如在插入时为5，则a [5] = 1；当删除时，例如5，则a [5] = 0;搜索时，例如，5，那么我可以简单地返回a [5]，对吧？

我知道这项练习比我想象的要难，但是这个问题的关键是什么？

Answer 1

基本上，您将实现一个有界大小的多集，其元素数量（#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,_,...]。

为什么这不起作用？例如，如果您插入5然后删除5，这似乎很好用，但是如果在未初始化的数组上执行 .search(5)会发生什么呢？明确告诉您无法初始化它，因此您无法分辨在该内存 e.g. 24753中找到的值是否实际上意味着“有24753个 5实例”或是否为垃圾。

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

如果您想要一个完整的解决方案，则可以将鼠标悬停在灰色方框上，以显示我提出的答案。只是几行代码，但证明要长一些：


扰流板：完整解决方案


建立：

使用N个单词作为调度表： locationOfCounts[i]是大小为N的数组，其值在 location=[0,M]范围内。这是 i计数的存储位置，但是只有当我们证明它不是垃圾时，我们才能信任该值。 >！
（旁注：这等效于一个指针数组，但是一个指针数组使您能够查找垃圾，因此必须使用指针范围检查对该实现进行编码。）


要找出集合中有多少 i个，可以从上方查找值 counts[loc]。我们使用M个单词作为计数本身： counts是大小为N的数组，每个元素有两个值。第一个值是它表示的数字，第二个值是该数字的计数（在[1，m]范围内）。例如，值 (5,2)表示集合中存储了2个实例 5。

（M个单词足够用于所有计数的空间。证明：我们知道绝对不能超过M个元素，因此最坏的情况是我们有M个value = 1的计数。QED）

（我们还选择仅跟踪计数> = 1，否则我们将没有足够的内存。）


使用一个称为 numberOfCountsStored的数字，该数字已初始化为0，但是每当项目类型的数量发生更改时都会更新。例如，对于 {}，此数字将为0，对于 {5:[1 times]}，此数字将为1，对于 {5:[2 times]}，则为2，对于 {5:[2 times],6:[4 times]}。


                          1  2  3  4  5  6  7  8...

locationOfCounts[<N]: [☠, ☠, ☠, ☠, ☠, 0, 1, ☠, ...]

counts[<M]:           [(5,⨯2), (6,⨯4), ☠, ☠, ☠, ☠, ☠, ☠, ☠, ☠..., ☠]

numberOfCountsStored:          2


下面我们刷新每个操作的详细信息，并证明其正确性：


算法：

有两个主要思想：1）我们永远不能先让我们自己读取内存，而不先确认不是垃圾，否则，我们必须能够证明它是垃圾，2）我们必须能够在< cc>初始化 O(1)内存的时间，且只有 counter空间。为此，我们使用的 O(1)空间是 O(1)。每次进行操作时，我们都会返回到该数字以证明一切正确（例如，参见下面的★）。表示形式不变是，我们将始终将计数从左到右存储在 numberOfItemsStored中，因此 counts将始终是有效数组的最大索引。


numberOfItemsStored-选中 .search(e)。现在我们假设该值已正确初始化并且可以信任。我们继续检查 locationsOfCounts[e]，但是首先我们检查 counts[loc]是否已初始化：如果0 <= counts[loc] << cc>则将其初始化（如果不是，则数据无意义，因此我们返回False）。检查后，我们查找 loc，这给了我们 numberOfCountsStored对。如果 counts[loc]！= number,count，我们通过遵循随机垃圾（无意义）到达此处，因此我们返回False（再次如上）……但是如果确实是 number == e，则证明该计数是正确的（★证明： number是该特定 e是有效的见证，而 numberOfCountsStored是 counts[loc]是有效的见证，因此我们最初的查找不是垃圾。），因此我们将返回真正。


counts[loc].number-执行 locationOfCounts[number]中的步骤。如果已经存在，则只需将计数加1。但是，如果不存在，则必须在 .insert(e)子数组右侧添加一个新条目。首先，我们增加 .search(e)以反映这一新计数有效的事实： counts。然后，我们添加新条目： numberOfCountsStored。最后，我们在调度表中添加对它的引用，以便我们可以快速地 loc = numberOfCountsStored++查找它。


counts[loc] = (e,⨯1)-执行 locationOfCounts[e] = loc中的步骤。如果不存在，则抛出错误。如果count> = 2，我们要做的就是将count减1。否则，count为1，这是确保整个 .delete(e)- .search(e)不变的技巧（即，所有内容都存储在左侧） numberOfCountsStored的一部分是执行交换。如果删除操作会删除最后一个元素，那么我们将丢失 counts[...]对，从而在数组 counts中留下一个漏洞。我们将此孔与最后一个countPair交换，将 counts减1以使该孔无效，并更新 [countPair0, countPair1, _hole_, countPair2, countPair{numberOfItemsStored-1}, ☠, ☠, ☠..., ☠]，现在它指向计数记录的新位置。