3

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

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

我的方法是：

1.对数组进行排序。

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

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

4

5 回答 5

3

如果你的“集合”只包含小整数，那么它们可以用一个计数数组来表示......例如，{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 更现代的语言中的任何一种，当然这些语言提供此类集合类型。

于 2013-03-28T08:11:47.043 回答
0

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

于 2013-03-28T05:38:01.920 回答
0

这是我的代码，用 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;
}
于 2013-03-28T05:59:59.820 回答
0

我建议您的解决方案的唯一优化是将您的数组（它们不是真正的集合，因为它们有重复项）转换为键值字典，以便键是数组的元素，值是数组的数量发生。对于您的测试示例： {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} - 您可以将其转换回数组。

于 2013-03-28T08:18:23.847 回答
0

其他人已经涵盖了通过计数数组或计数图来表示每个“集合”（或更正式地，“袋子”）的想法。如果有很多重复，并且每个包没有那么多钥匙，这将特别有用。给定 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最小唯一元素计数的大小。

在数据库查询优化期间进行了类似的操作，以大大提高查询时间。

于 2018-11-13T11:40:52.613 回答