基本上，您将实现一个具有大小限制的多重集，其元素数量（#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)初始化空间，否则问题将无法解决。（否则，a便.search()无法将内存中的随机垃圾与实际数据区分开，因为您总是会想出看起来像实际数据的随机垃圾。）例如，您可能考虑使用一个布尔值，这意味着“我已经开始使用我的记忆”，您将其初始化为False，并在开始写入m记忆字时将其设置为True
。

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

SPOILER：完全解决方案

设置 ：
使用N个单词作为调度表： locationOfCounts[i]
是大小为N的数组，其值在范围内location=[0,M]。这是i将存储计数的位置，但是只有当我们 证明
它不是垃圾时，我们才能信任该值。>！
（旁注：这相当于数组的指针，但指针数组暴露你能看垃圾，所以你不得不代码，实现与指针的范围检查。）

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

使用一个称为 numberOfCountsStored IS 的数字，该数字被初始化为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]因此它现在指向计数记录的新位置。