代码之家 › 专栏 › 技术社区 › Imbue

两个集合是否相交的算法

language-agnostic algorithm

Imbue · 技术社区 · 17 年前

假设我有两个数组:

Int Arraya[]=5、17、150、230、285

内线[]=7、11、57、110、230、250

这两个数组都经过排序,可以是任意大小。我正在寻找一种有效的算法来确定数组之间是否包含任何重复的元素。我只想得到一个正确/错误的答案,我不在乎共享哪个元素或共享多少元素。

天真的解决方案是循环遍历arraya中的每个项,并执行 binary search 因为它在阿拉比。我相信这种复杂性是O(m*log n)。

因为这两个数组都是排序的,所以似乎应该有一个更有效的算法。

我还想要一个不假定数组包含数字的通用解决方案(也就是说,该解决方案也适用于字符串)。但是,比较运算符定义得很好,两个数组都是从最小到最大排序的。

7 回复 | 直到 8 年前

Andru Luvisi 17 年前

假设您正在进行合并排序,但不要将结果发送到任何位置。如果你到达任意一个源的末尾,就没有交集。每次比较每个元素的下一个元素时,如果它们相等,就会有一个交集。

例如:

counterA = 0;
counterB = 0;
for(;;) {
    if(counterA == ArrayA.length || counterB == ArrayB.length)
        return false;
    else if(ArrayA[counterA] == ArrayB[counterB])
        return true;
    else if(ArrayA[counterA] < ArrayB[counterB])
        counterA++;
    else if(ArrayA[counterA] > ArrayB[counterB])
        counterB++;
    else
        halt_and_catch_fire();
}

David Nehme 17 年前

因为有人想知道STL。开箱即用,集合交集算法会比你想要的做得更多:它会找到所有的公共值。

    #include <vector>
    #include <algorithm>
    #include <iterator>
    using namespace std;
//    ...    
      int ArrayA[] = {5, 17, 150, 230, 285};
      int ArrayB[] = {7, 11, 57, 110, 230, 250};
      vector<int> intersection;
      ThrowWhenWritten output_iterator;
        set_intersection(ArrayA, ArrayA + sizeof(ArrayA)/sizeof(int),
                         ArrayB, ArrayB + sizeof(ArrayB)/sizeof(int),
                         back_insert_iterator<vector<int> >(intersection));

        return !intersection.empty();

这在O(M+N)时间内运行,但它需要存储所有重复项,并且在找到第一个重复项时不会停止。

现在,从GNU修改代码 implementation 在STL中,我们可以更精确地得到你想要的。

 template<typename InputIterator1, typename InputIterator2>
 bool 
 has_intersection(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2)
    {
       while (first1 != last1 && first2 != last2) 
       {
          if (*first1 < *first2)
             ++first1;
          else if (*first2 < *first1)
             ++first2;
          else
             return true;
       }
       return false;
}

DavidLG 17 年前

如果一个列表比另一个短得多,那么二进制搜索就是解决问题的方法。如果列表的长度相似,并且您对O(M+N)满意,那么标准的“合并”就可以了。有更复杂的算法更灵活。我在自己的搜索中发现的一篇论文是:

http://www.cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf

aku 17 年前

如果您不关心内存消耗,那么可以通过使用哈希来获得良好的性能,即使用键=一个数组的值创建哈希,并针对该哈希测试第二个数组的值。

JaredPar 17 年前

如果您使用的是C 3.0,那么为什么不在这里利用LINQ呢?

ArrayA.Intersect(ArrayB).Any()

这不仅是通用的(适用于任何可比较的类型),引擎盖下的实现也相当有效(使用哈希算法)。

Mr Fooz 17 年前

如果值的范围很小,可以为其中一个值(时间成本=o(n))建立一个查找表,然后检查是否从另一个列表中设置了位(时间成本=o(n))。如果范围很大,可以对哈希表执行类似的操作。

格米克的合并分类技巧是一个更好的主意。

James Curran 17 年前

戈梅克走上了正确的道路,但有点忽略了算法。

首先比较arraya[0]和arrayb[0]。如果它们相等,你就完了。如果arraya[0]小于arrayb[0],则移动到arraya[1]。如果arraya[0]大于arrayb[0],则移动到arrayb[1]。

一直往前走直到到达一个数组的末尾或者找到一个匹配项。