两个排序数组的交集

Question

给出两个排序的数组:A和B.阵列的大小A是La与阵列的大小B是Lb.如何找到A和B？

如果La比大得多Lb,那么交点查找算法会有什么不同吗？

Answer 1

因为这看起来像一个HW ......我会给你算法:

Let arr1,arr2 be the two sorted arrays of length La and Lb.
Let i be index into the array arr1.
Let j be index into the array arr2.
Initialize i and j to 0.

while(i < La and j < Lb) do

    if(arr1[i] == arr2[j]) { // found a common element.
        print arr[i] // print it.
        increment i // move on.
        increment j
    }
    else if(arr1[i] > arr2[j])
        increment j // don't change i, move j.
    else
        increment i // don't change j, move i.
end while

Answer 2

我一直在努力解决同样的问题,到目前为止,我带来了:

1. 线性匹配,在最坏的情况下会产生O(m + n).你基本上保留两个指针(A和B),每个指针指向每个数组的开头.然后前进指向较小值的指针,直到到达一个数组的末尾,这表示没有交集.如果在任何时候你有*A ==*B - 这是你的交叉点.

2. 二进制匹配.在最坏的情况下产生~O(n*log(m)).您基本上选择较小的数组并在较小数组的所有元素的较大数组中执行二进制搜索.如果你想要更加花哨,你甚至可以使用二进制搜索失败的最后位置,并将其用作下一个二进制搜索的起点.这样你可以略微改善最坏情况但是对于某些套装它可能会创造奇迹:)

3. 双二进制匹配.它是常规二进制匹配的变体.基本上你从较小的数组中间获取元素并在更大的数组中进行二进制搜索.如果你什么都没找到,那么你将较小的数组切成两半(是的,你可以抛弃你已经使用过的元素)并将更大的数组切成两半(使用二进制搜索失败点).然后重复每一对.结果比O(n*log(m))好,但我懒得计算它们是什么.

这是最基本的两个.两者都有优点.线性更容易实现.二进制可以说更快(尽管有很多情况下线性匹配将胜过二进制).

如果有人比我更了解我想听的话.匹配数组是我现在所做的.

PS没有引用我的术语"线性匹配"和"二进制匹配",因为我自己制作它们并且可能已经有了它的名字.

Answer 3

set_intersection在这里使用.通常的实现类似于merge-sort算法的合并部分.