查找两组相交的算法

假设我有两个数组:

int ArrayA [] = {5,17,150,230,285};

int ArrayB [] = {7,11,57,110,230,250};

两个数组都是排序的,可以是任何大小.我正在寻找一种有效的算法来查找数组是否包含它们之间的任何重复元素.我只想要一个真/假答案,我不关心共享哪个元素或多少元素.

天真的解决方案是循环遍历ArrayA中的每个项目,并在ArrayB中对其进行二进制搜索.我相信这种复杂性是O(m*log n).

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

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

1> Andru Luvisi..：

---

假装您正在进行合并,但不要将结果发送到任何地方.如果到达任一源的末尾,则没有交集.每次比较每个元素的下一个元素时,如果它们相等,则存在交集.

例如:

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();
}

---

一个狡辩:我鄙视无限循环.而不是"for(;;)",这应该是"while(counterA!= ArrayA.length && counterB!= ArrayB.length)"(消除第一个if())

---

轻微的狡辩:O(n)=== O(m + n) - 大O符号用于[算法的复杂性顺序](http://rob-bell.net/2009/06/a-beginners-guide -to-big-o-notation /),不是绝对的衡量标准.O(n)简单地说算法是线性的 - 你将在每个元素上迭代一次.n的大小无关紧要.

---

或者是O(m + n)？

2> David Nehme..：

---

因为有人想知道stl.开箱即用的set_intersection算法会比你想要的更多:它会找到所有常见的值.

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

        return !intersection.empty();

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

现在,从stl 的gnu 实现修改代码,我们可以更准确地得到你想要的.

 template
 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;
}