algorithm - 多集相交的算法模型

我的问题是，我们怎样才能申请5~7组的交集。假设每个集合都有一组元素请帮助我创建一个算法，这将是这个过程的复杂性。

最佳答案

假设集合的元素可以散列，并且您有一些散列键工具，比如字典（或者可以创建自己的散列键工具，这并不难）：

List<Set<element-type>> sets;    \\your list of sets to intersect

int size = SUM{List[*].Count};  \\ size for the hash
Dictionary<element-type,int> Tally = New Dictionary<element-type,int>(size);

// Add all elements to the Tally hash
foreach set in sets
{
    foreach e in set
    {
        if (Tally.Exists(e))
            Tally[e]++;
        else
            Tally.Add(e,1);
    }
}

//Now, find the Tally entries that match the number of sets
foreach kvp in Tally.KeyValuePairs
{
    If (kvp.Value == sets.Count)
        // add the Key to output list/set
        Output.Add(kvp.Key);
}

这具有运行时复杂度o（n），其中“n”是所有集合中元素的数目。