1

什么是查找元素属于哪个集合的良好数据结构，将 N 个项目分组到 M 个不同的集合中？例如，如果集合是 {A,B} , {C,D,E}, {F,G} 我怎样才能找到给定“D”的集合？这些集合是散列集合，因此集合内的包含查询是 O(1)。

如果我只是在集合列表中有集合，

[{A,B}, {C,D,E}, {F,G}]

我可以通过询问列表中的每个集合是否包含该项目来进行查找。这很容易实现，运行时间是线性的（以集合的数量计）。

一种更快的方法是将所有集合存储在哈希表中，以每个集合中的每个项目为键。那是：

[A -> {A, B},
 B -> {A, B},
 C -> {C, D, E},
 D -> {C, D, E},
 E -> {C, D, E}, 
 F -> {F, G}, 
 G -> {F, G}]

这种结构让我可以在 O(1) 时间内检索到正确的集合，但感觉效率低下且丑陋。是否有更好的数据结构允许 O(1) 查找正确的集合？我应该通过像一种布隆过滤器一样组合散列来制作查找键吗？其他想法？

4

1 回答 1

0

你可以这样实现：

您将需要一系列树。index 将是设置的数字。

有一个哈希表来存储整个列表中每个元素的（元素，索引）对。

对于每个集合，您可以使用树结构，唯一标识符是根，列表的元素连接到根。

于 2013-05-01T18:19:01.830 回答