如何设计一个允许在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,那么我可以简单地返回[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()将无法区分随机垃圾在你的记忆,从实际的数据,因为你总是可以想出看起来像实际数据随机的垃圾.)例如,你可以考虑有一个boolean,这意味着"我一直在使用开始我的记忆"你初始化为False,并在你开始写你m的记忆的那一刻设置为True .

如果你想要一个完整的解决方案,你可以将鼠标悬停在灰色块上以显示我想出的那个.它只有几行代码,但证明有点长:

SPOILER:FULL SOLUTION

设置:
使用N个字作为调度表:locationOfCounts[i]是一个大小为N的数组,其值在该范围内location=[0,M].这是i存储计数的位置,但是如果我们能够证明它不是垃圾,我们只能信任这个值.>!
(旁注:这相当于数组的指针,但指针数组暴露你能看垃圾,所以你必须将代码与指针的范围检查,落实.)

要找出多少i那儿有在集合中,您可以counts[loc]从上面查找值.我们使用M个单词作为计数本身:counts是一个大小为N的数组,每个元素有两个值.第一个值是它代表的数字,第二个值是该数字的计数(在[1,m]范围内).例如,值(5,2)将意味着5该集合中存储了2个数字实例.
(M字对于所有计数足够的空间.证明:我们知道不能超过M个元素较多,因此最坏的情况是我们的价值= 1 QED中号数.)
(我们也可以选择只保持跟踪count> = 1,否则我们没有足够的内存.)

使用一个名为numberOfCountsStoredIS 的数字初始化为0,但只要项目类型的数量发生变化就会更新.例如,此数字为0表示{},1表示{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)我们需要能够及时证明O(1)这块counter内存已被初始化,只有O(1)空间.为此,O(1)我们使用的空间是numberOfItemsStored.每次我们进行操作时,我们都会回到这个数字来证明一切都是正确的(例如见下面的★).表示不变量是我们将始终存储counts从左到右的计数,因此numberOfItemsStored将始终是有效的数组的最大索引.

.search(e)- 检查locationsOfCounts[e].我们现在假设该值已正确初始化并且可以信任.我们继续检查counts[loc],但首先我们检查是否counts[loc]已初始化:如果0 <= loc< numberOfCountsStored则初始化(如果不是,则数据是无意义的,因此我们返回False).在检查之后,我们查找counts[loc]它给了我们一number,count对.如果number!= e,我们通过跟随随机垃圾(荒谬)来到这里,所以我们返回False(再次如上)...但如果确实number== e,这证明计数是正确的(★证明:证明numberOfCountsStored这个特殊的counts[loc]是有效的,并且counts[loc].number是一个有效的证人,locationOfCounts[number]因此我们的原始查找不是垃圾.),所以我们将返回True.

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

.delete(e)- 执行步骤.search(e).如果它不存在,则抛出错误.如果计数> = 2,我们需要做的是减1计数,否则计数为1,这里的伎俩,以确保整个numberOfCountsStored- counts[...]不变(即一切仍然存储在左边部分counts)被执行掉期交易.如果删除将删除最后一个元素,我们将失去一counts对,在我们的数组中留下一个洞:[countPair0, countPair1, _hole_, countPair2, countPair{numberOfItemsStored-1}, ?, ?, ?..., ?].我们用最后一次countPair交换这个洞,减少numberOfCountsStored使洞无效,然后更新,locationOfCounts[the_count_record_we_swapped.number]以便它现在指向计数记录的新位置.