algorithm - 用于检查 O(1) 时间内元素数量是否相等的数据结构？

Question

检查不同类型对象的元素数量是否相同的最佳数据结构是什么？

例如，如果我有

2个

3个b

3 个

不同类型对象的元素个数是不一样的。

如果我有

2个

2个b

2个c

那么这个是一样的

允许您在 O(1) 时间内完成此操作的最佳数据结构是什么？您将如何实现它？

Answer 1

一种方法是使用两个字典来动态地在 O(1) 中完成它。

第一个将每种类型映射到一个计数，{a:2,b:3,c:3}。第二个将每个计数映射到一组具有该计数的类型。 {2:{a},3:{b,c}}。如果第二个字典的大小小于 2(0 或 1)，那么显然所有类型都具有相同的计数，如果不是这种情况，则该字典中至少有两个键项对，假设字典当计数改变时更新。

• 添加一个类型意味着将它添加到每个字典中。
• 删除一个类型意味着从每个字典中删除它。
• 更新类型需要先更新第二个字典，方法是删除先前的计数(从第一个字典获得)并添加当前计数，然后更新第一个字典。