找到集合的交集。

Question

我们有n个不同大小的整数集合，每个集合中可能包含重复元素。我需要找到这些集合的交集。如果一个元素在所有集合中都出现了多次，它应该被添加到结果中。

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

我的方法是：

1.对数组进行排序。

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

是否有更高效的方法来找到交集呢？

- poorvank

---

那看起来非常接近最优解。 - Patashu

在数学中，集合不包含重复元素；而多重集合或袋子可以包含重复元素。 - Jonathan Leffler

使用多核处理器，也许可以采用并行插入排序（当然，您的数据必须足够大才值得这样做）。 - kfmfe04

{0,5,5,3,4}, {1,3,5,5,6}, and {3,5,5} 不是集合。如果您真的在处理集合，最有效的实现方法是使用位数组。 - Jim Balter

“有没有更有效的方法来找到交集？”--确实有；请看我的答案。 - Jim Balter

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更现代的语言，这些语言当然提供这样的集合类型。

- Jim Balter

Answer 2

你可以为每个数组创建一个字典，遍历每个数组并将其计数器加上，如果检测到新数字，则添加到“全局”字典中。然后，从“全局”字典中选择下一个数字（它保证至少存在于一个计数器字典中），然后获取所有计数器的最小值。当然，如果在单个字典中遇到空值，则不将该数字添加到结果中。否则，将“找到的最小值”数量的“数字”添加到结果数组中。使用这样的字典结构，算法的完整复杂度约为O(n*m)，其中M是集合大小的最大值，N是集合的数量，而如果对集合进行排序，则复杂度为O(n*m*log(m))，如果每个集合包含超过1000个元素，则复杂度会更高。

- Vesper

---

我认为将集合数量乘以最大集合容量并不正确，因为最终你会添加比实际存在的更多的元素。我认为时间复杂度应该是 O(n)，其中 n 为所有集合中元素的数量。 - Khaled.K

@KhaledAKhunaifer 我们必须查询这些集合中的每个元素，以便正确地形成结果，它们最多为n*m，因此我们无法获得小于此的O()函数。 M不是“集合容量”，而是算法开始时给出的最大值。集合容量可以达到2^32，例如，集合本身的大小为5。 - Vesper

在 map-of-counts 中，同时使用 m 表示袋子大小和唯一键的数量会令人困惑。 - tucuxi

Answer 3

其他人已经讲述了用计数数组或计数映射来表示每个“集合”（或更正式地说，“袋子”）的想法。如果存在大量重复，并且每个袋子中的键不是很多，这种方法特别有用。给定N个包，每个包含M个元素，其中K个是不同的，则将其转换为数组/映射表示并生成结果的复杂度为O(N x M) + O(N x K)。请注意，反复查找B个包的交集只需要O(B x K)，因为您可以重复使用映射表示。

如果您正确地排序成对的交集，还可以获得很高的效率。例如，如果其中一个包只包含单个元素，则只有两个可能的答案：所有其他包也都包含该元素（结果是该元素本身），或者至少有一个包不包含该元素。这将使您完全忽略其他集合的其余内容。在这种极端情况下，实际交集的运行时间将降至O(N)，提高了K倍。

一般来说，如果袋子中有大量不同数量的唯一元素，按照递增大小（唯一元素数量）对它们的映射进行排序会增加O(N log N)的成本，但可以在计算交集时跳过很多键，将交集时间降低到O(N x K_min)，其中K_min是最小唯一元素计数的大小。

在数据库查询优化期间也会执行类似的操作，以极大地提高查询时间。

- tucuxi

Answer 4

这是我的代码，使用C99编译（不要忘记先实现get、insert、remove函数）：

struct MyNode { MyNode * next; int value; int frequency; }

// returns MyNode pointer when value exist
MyNode * get(MyNode * head, int val);

// insert a new value, with frequency = 1
void insert(MyNode * head, int val);

// remove an element from the linked-list
bool remove(MyNode * head, int val);

int * intersection (int ** set, int w, int * h)
{
    MyNode * head = 0;
    MyNode * temp = 0;
    int finalSize = 0;
    int k = 0;

    for (int i=0; i<w; i++)
    {
        for (int j=0; j<h[i]; j++)
        {
            temp = get(head, set[i][j]);

            if (temp == 0)
            {
                insert(head, set[i][j]);
                finalSize++;
            }
            else
            {
                temp->frequency++;
            }
        }
    }

    temp = head;
    while (temp != 0)
    {
        if (temp->frequency != w)
        {
            temp = temp->next;
            remove(head, temp->value);
            finalSize--;
        }
        else
            temp = temp->next;
    }

    int * intersection = (int*)malloc(finalSize*sizeof(int));

    temp = head;
    while (temp != 0)
    {
        intersection[k++] = temp->data;
        temp = temp->next;
    }

    return intersection;
}

- Khaled.K

Answer 5

我唯一建议你的解决方案进行的优化是将数组（它们实际上不是集合，因为它们有重复项）转换为键值字典，以便键是数组元素，值是出现次数。对于你的测试例子：{0,5,5,3,4} {5,2,3,5,6} {1,3,5,5,6}，字典看起来像这样。

{0 => 1, 3 => 1, 4 => 1, 5 => 2}
{2 => 1, 3 => 1, 5 => 2, 6 => 1}
{1 => 1, 3 => 1, 5 => 2, 6 => 1}

然后你比较一对字典，从最小的字典开始，如果元素在两个字典中都出现了，就取较小的出现次数。这种优化将节省处理重复项所需的时间。

结果的字典将是：{3 => 1, 5 => 2} - 你可以将它转换回数组。

- PanJanek