java - C++/ java : Efficiently find a set in the collection containing given value

Question

假设我们有一组互斥集合
{A,B,C,D} 其中 A = {1,2,3}，B = {4,5,6}，C = {7,8,9}, D = {10,11,12}
给定一个值 Z，例如 3，我希望它返回集合 A 的索引，因为 A 的成员是 3。

问题是我如何使用 C++ 或 JAVA 高效地完成它。

我当前的解决方案:将 A、B、C、D 作为 HashSet(或 C++ 中的 unordered_set)存储在容器中并循环遍历每个集合，直到包含 Z 找到了。
问题在于容器中存储的集合数量的复杂度为 O(n)。

有什么方法(或任何数据结构来存储这些集合)比 O(n) 更快地做到这一点吗？

Answer 1

您可以创建一个将值映射到集合 id 的映射(例如，它应该将 1、2、3 映射到 A，将 4、5 和 6 映射到 B 等等)。使用 HashMap ，它可以平均在 O(1) 内工作。