两个有序数组的交集。

Given two sorted arrays: A and B. The size of array A is La and the size of array B is Lb. How to find the intersection of A and B?

给定两个排序数组:A和B，数组A的大小是La，数组B的大小是Lb，如何找到A和B的交集?

If La is much bigger than Lb, then will there be any difference for the intersection finding algorithm?

如果La比Lb大得多，那么交集查找算法会有什么不同吗?

6 个解决方案

#1

Use set_intersection as here. The usual implementation would work similar to the merge part of merge-sort algorithm.

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

#2

Since this looks like a HW...I'll give you the algorithm:

因为这看起来像一个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

#3

I've been struggling with same problem for a while now, so far I came with:

我在同一问题上挣扎了一段时间，到目前为止

Linear matching which will yield O(m+n) in worst case. You basically keep two pointers (A and B) each pointing to beginning of each array. Then advance pointer which points to smaller value, until you reach end of one of arrays, that would indicate no intersection. If at any point you have *A == *B - here comes your intersection.

在最坏情况下，线性匹配将产生O(m+n)。你基本上保持两个指针(A和B)指向每个数组的开始。然后将指针指向更小的值，直到你到达数组的末尾，表示没有交集。如果在任意点有*A = *B -这就是你的交点。
Binary matching. Which yields ~ O(n*log(m)) in worst case. You basically pick smaller array and perform binary search in bigger array of all elements of the smaller array. If you want to be more fancy, you can even use last position where binary search failed and use it as starting point for next binary search. This way you marginally improve worst case but for some sets it might perform miracles :)

二元匹配。在最坏情况下，它的收益率是~ O(n*log(m))。你可以选择更小的数组并在更大的数组中执行二进制搜索。如果你想要更花哨一点，你甚至可以使用上一个位置，即二分查找失败，并将它用作下一个二分查找的起点。这样你就能稍微改善最坏的情况，但对某些人来说，这可能会带来奇迹:)
Double binary matching. It's a variation of regular binary matching. Basically you get element from the middle of smaller array and do binary search in bigger array. If you find nothing then you cut smaller array in half (and yes you can toss element you already used) and cut bigger array in half (use binary search failure point). And then repeat for each pair. Results are better than O(n*log(m)) but I am too lazy to calculate what they are.

双重二元匹配。它是常规二进制匹配的变体。从更小的数组中获取元素并在更大的数组中进行二进制搜索。如果你没有找到任何东西，那么你就可以将更小的数组分成两半(是的，你可以把你已经用过的元素扔进去)，然后把更大的数组分成两半(使用二分查找失败点)。然后对每一对重复。结果比O(n*log(m))好，但我懒得计算它们是什么。

Those are two most basic ones. Both have merits. Linear is a bit easier to implement. Binary one is arguably faster (although there are plenty of cases when linear matching will outperform binary).

这是最基本的两个。都有优点。线性更容易实现。二进制文件可以说更快(尽管有很多情况下线性匹配的性能优于二进制)。

If anyone knows anything better than that I would love to hear it. Matching arrays is what I do these days.

如果有谁比我知道的更好的话，我愿意听。匹配数组是我现在所做的。

P.S. don't quote me on terms "linear matching" and "binary matching" as I made them up myself and there are probably fancy name for it already.

附注:不要用“线性匹配”和“二进制匹配”来引用我，因为我自己编的，而且可能已经有了花哨的名字。

#4

void Intersect()
{
    int la, lb;
    la = 5;
    lb = 100;
    int A[5];
    int i, j, k;
    i = j = k = 0;
    for (; i < 5; ++i)
        A[i] = i + 1;
    int B[100];
    for (; j < 100; ++j)
        B[j] = j + 2;
    int newSize = la < lb ? la : lb;
    int* C = new int[newSize];
    i = j = 0;
    for (; k < lb && i < la && j < lb; ++k)
    {
        if (A[i] < B[j])
            i++;
        else if (A[i] > B[j])
            j++;
        else
        {
            C[k] = A[i];
            i++;
            j++;
        }
    }
    for (k = 0; k < newSize; ++k)
        cout << C[k] << NEWLINE;
}

#5

Let's consider two sorted arrays: -

让我们考虑两个排序的数组:-。

int[] array1 = {1,2,3,4,5,6,7,8};
int[] array2 = {2,4,8};

int i=0, j=0;    //taken two pointers

While loop will run till both pointers reach up to the respective lengths.

While循环将运行，直到两个指针达到各自的长度。

while(i<array1.length || j<array2.length){
    if(array1[i] > array2[j])     //if first array element is bigger then increment 2nd pointer
       j++;
    else if(array1[i] < array2[j]) // same checking for second array element
      i++;
    else {                         //if both are equal then print them and increment both pointers
        System.out.print(a1[i]+ " ");

        if(i==a1.length-1 ||j==a2.length-1)   //one additional check for ArrayOutOfBoundsException
            break;
        else{
            i++;
            j++;
        }
    }
}

Output will be: -

输出将:-

2 4 8

#6

-1

 //intersection of two arrays
#include<iostream>
using namespace std;
int main() {

int i=0,j=0,m,n;
int arr1[i],arr2[j];
cout<<"Enter the number of elements in array 1: ";
cin>> m;
cout<<"Enter the number of elements in array 2: ";
cin>>n;
for (i=0;i<m;i++){
    cin>> arr1[i];
}
for(j=0;j<n;j++){
    cin>> arr2[j];
}
for(j=0;j<n;j++){
    for(i=0;i<m;i++) {
        if (arr1[i] == arr2[j]){
        cout<< arr1[i];
        cout << ' ';
        break;
        }
    } 
 }    

 return 0;
 }

#1