寻找两个集合是否相交的算法

Question

假设我有两个数组：

int ArrayA[] = {5, 17, 150, 230, 285}; int ArrayB[] = {7, 11, 57, 110, 230, 250};

这两个数组都是排序好的，长度可以任意。我正在寻找一种有效的算法来查找它们之间是否存在任何重复元素。我只需要一个真/假答案，不关心共享哪个元素或有多少个。

朴素的解决方案是遍历ArrayA中的每个项，并在ArrayB中进行二分搜索。我认为这个复杂度是O(m * log n)。

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

我还希望有一个通用的解决方案，不假定数组保存数字（即解决方案也适用于字符串）。但是，比较运算符已经定义好了，两个数组都是从最小到最大排序的。

- Imbue

---

只是一点小提醒，我们说你在这里概述的解决方案的复杂度为O(m * log n)，其中m和n是两个数组的大小。 - Bill the Lizard

我有一种感觉就是这样。谢谢。 - Imbue

Answer 1

假设你正在进行归并排序，但不要将结果发送到任何地方。如果您到达任一源的末尾，则不存在交集。每次比较每个元素的下一个元素时，如果它们相等，则存在交集。

例如：

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

- Glomek

---

我倾向于认为复杂度为 O(m+n)。m和n可以是非常不同的大小（例如，m = n ^ 2），而O(m+n)等价于O(max(m,n))。 - Matt J

一点疑问：我讨厌无限循环。应该使用“while(counterA != ArrayA.length && counterB != ArrayB.length)”代替“for(;;)”（消除第一个if()）。 - James Curran

詹姆斯：在我看来，你应该把条件放在循环的顶部，而“return false;”则放在循环结束之后。这个版本让我喜欢的一件事情是将条件和返回语句放在一起。 - Andru Luvisi

实际上，它的时间复杂度是O(n+m)，没有任何绕过它的方法。考虑数组[1,2,3...99,100]和[50,101]。在终止之前，它将不得不查看所有102个数组元素。 - James Curran

小小的疑惑：O(n) === O(m + n) - 大O符号用于算法复杂度的阶数，并不是绝对的度量。O(n)只是表示算法是线性的——您将依次迭代每个元素。n的大小并不重要。 - HerbCSO

Answer 2

有人对stl产生了疑问。开箱即用的set_intersection算法会做更多的事情：它会找到所有共同的值。

    #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 stl的实现代码implementation，我们可以更精确地得到您想要的结果。

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

- David Nehme

---

虽然很简单易懂，但我不会使用你从GNU复制的名称。STL实现允许使用这些符号，但POD（普通老式开发人员）不允许使用（双下划线和大写下划线对于实现已经解决）。 - Motti

Answer 3

如果一个列表比另一个列表短得多，那么二分查找是最好的选择。如果两个列表长度相似，并且您满意 O(m+n) 的时间复杂度，则标准的“合并”方法可以使用。还有更灵活的算法。我在自己的搜索中发现了一篇论文：

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

- DavidLG

Answer 4

如果您不关心内存消耗，可以通过使用哈希表来获得良好的性能。即创建一个哈希表，将一个数组的值作为键，然后将第二个数组的值与该哈希表进行比较。

- aku

---

将两个数组中较小的一个进行哈希，以节省最多的内存。这个解决方案肯定会非常快速。 - Bill the Lizard

Answer 5

如果你正在使用C# 3.0，为什么不在这里利用LINQ呢？

ArrayA.Intersect(ArrayB).Any()

这不仅是通用的（适用于任何可比较类型），而且底层实现非常高效（使用哈希算法）。

- JaredPar

Answer 6

如果值的范围很小，您可以为其中一个构建查找表（时间成本= O（N）），然后检查另一个列表中是否设置了该位（时间成本= O（N））。 如果范围很大，您可以使用哈希表进行类似的操作。

Glomek的归并排序技巧是一个更好的想法。

- Mr Fooz

Answer 7

Glomek的想法是对的，但他有点忽略了算法。

首先比较ArrayA [0]和ArrayB [0]。如果它们相等，那么你就完成了。 如果ArrayA [0]小于ArrayB [0]，则移动到ArrayA [1]。 如果ArrayA [0]大于ArrayB [0]，则移动到ArrayB [1]。

继续这样比较，直到达到一个数组的末尾或找到匹配项为止。

- James Curran