c - 找到集合的交集

Question

我们给定了 n 组不同大小的整数。每个集合也可以包含重复项。我必须找到集合的交集。如果某个元素在所有集合中多次出现，则应将其添加到结果中。

例如，考虑三个集合 {0,5,5,3,4} {5,2,3,5,6} {1,3,5,5,6}。给定集合的交集应该是 {3,5,5}

我的方法是:

1.对数组进行排序。

2.比较从最小数组开始的每个元素并更新计数。

有没有更有效的方法来找到交叉点？

Answer 1

如果您的“集合”只包含小整数，那么它们可以用计数数组表示……例如，{5,2,3,5,6} 是

index 0 1 2 3 4 5 6
count 0 0 1 1 0 2 1

这些集合的交集是计数的最小值:

      index 0 1 2 3 4 5 6
            -------------
{0,5,5,3,4} 1 0 0 1 1 2 0
{5,2,3,5,6} 0 0 1 1 0 2 1
{1,3,5,5,6} 0 1 0 1 0 2 1  
min         0 0 0 1 0 2 0 = {3,5,5}

如果值不是小整数但数量很少，则只需保留一个值数组——用作值和小整数之间的映射，小整数是数组的索引。

如果有太多的值以至于每个集合都有一个计数数组太昂贵了，请使用从值到计数的映射来表示每个“集合”，以及值的数组......然后迭代数组以生成每个值，遍历映射以获取计数并计算它们的最小值。为此，您需要一个哈希表或二叉树库来实现这些映射……或者使用比 C 更现代的语言中的任何一种，这些语言理所当然地提供此类集合类型。