算法找到，如果两套相交 [英] Algorithm to find if two sets intersect

问题描述

让我们说我有两个数组：

Let's say I have two arrays:

INT Arraya酒店[] = {5，17，150，230，285};

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

INT ArrayB的[] = {7，11，57，110，230，250};

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

两个数组进行排序，并且可以是任何尺寸。我在寻找一个有效的算法发现，如果数组包含它们之间的任何重复的元素。我只想要一个真/假答案，我不在乎哪个元素是共享还是多少。

Both arrays are sorted and can be any size. I am looking for an efficient algorithm to find if the arrays contain any duplicated elements between them. I just want a true/false answer, I don't care which element is shared or how many.

天真的解决方案是遍历Arraya酒店的每个项目，并做了二进制搜索它在ArrayB的。我相信这复杂度为O（M * log n）的。

The naive solution is to loop through each item in ArrayA, and do a binary search for it in ArrayB. I believe this complexity is O(m * log n).

由于两个数组进行排序，好像应该有一个更有效的算法。

Because both arrays are sorted, it seems like there should be a more efficient algorithm.

我也想不假设数组持有数量的通用解决方案（即解决方案应该也适用于字符串）。但是，比较操作的明确界定和两个数组排序从低到最大的。

I would also like a generic solution that doesn't assume that the arrays hold numbers (i.e. the solution should also work for strings). However, the comparison operators are well defined and both arrays are sorted from least to greatest.

谢谢！

推荐答案

pretend你正在做一个合并，但不要在任何地方发送结果。如果你到任何来源的结尾，没有交集。每次比较每个的下一个元素，如果它们相等，有一个交叉点

Pretend that you are doing a mergesort, but don't send the results anywhere. If you get to the end of either source, there is no intersection. Each time you compare the next element of each, if they are equal, there is an intersection.

例如：

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

这篇关于算法找到，如果两套相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！