两个排序数组的交集

使用 set_intersection 作为 here . 通常的实现与merge-sort算法的merge部分类似。

因为这看起来像一个硬件…我会给你算法:

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

我已经在同一个问题上挣扎了一段时间了,到目前为止我发现:

1. 最坏情况下产生o(m+n)的线性匹配。基本上保持两个指针(a和b)分别指向每个数组的开头。然后向前移动指针,指针指向较小的值,直到到达其中一个数组的末尾,这表示没有交点。如果在任何一点上你有*A==*B-这就是你的交叉点。

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

3. 双二进制匹配。它是常规二进制匹配的变体。基本上是从较小数组的中间获取元素,然后在较大数组中执行二进制搜索。如果找不到任何东西,则将较小的数组切成两半(是的,您可以丢弃已使用的元素),将较大的数组切成两半(使用二进制搜索失败点)。然后对每一对重复。结果比o(n*log(m))好,但我懒得计算它们是什么。

这是最基本的两个。两者都有优点。线性比较容易实现。二值匹配可以说更快(尽管有很多情况下线性匹配会优于二值匹配)。

如果有人比这更清楚的话,我很想听。匹配数组是我现在做的事情。

P.S.不要用“线性匹配”和“二进制匹配”来引用我的话,因为我是自己编的,可能已经有了一个很好的名字了。

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

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

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

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

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

输出为:

2 4 8

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