您要做的是基本上实现了一个多重集合,并且有限制的大小,既有元素数量(#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
内存