两个排序阵列的交集

给定两个排序阵列：A和B。阵列A的大小为La，阵列B的大小为Lb。如何找到交点A和B？两个排序阵列的交集

如果La比Lb大得多，那么交叉点搜索算法会有什么区别吗？

来源

2010-03-08 user288609

我们不会做你的功课，你 – shoosh 2010-03-08 08:55:58

这是一个面试问题。 – user288609 2010-03-08 09:17:53

现在做家庭作业，5年后它会成为你的同事，你会做它的工作，或者更糟的是调试它的工作。 – Guge 2010-03-08 09:19:17

使用set_intersection作为here。通常的实现将类似于合并排序算法的合并部分。

来源

2010-03-08 09:04:34

我觉得有趣的是，没有人问过比较数组元素的代价。使用立即数据类型（例如int或float），比较便宜并且set_intersection算法很好。但是，如果它是一个复杂的数据类型，比较两个元素的代价很高，我会使用散列技术。 – 2012-10-10 18:08:07

@fearless_fool你说得对。一个相关的问题：http://stackoverflow.com/questions/896155/tr1unordered-set-union-and-intersection – 2012-10-13 03:06:00

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

来源

2010-03-08 09:11:46 codaddict

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

来源

2010-03-08 11:54:42

我一直在努力与同样的问题，而现在，到目前为止，我想出了：

线性匹配在最差情况下将产生O（m + n）。基本上保持两个指针（A和B），每个指针指向每个数组的开头。然后前进指向较小值的指针，直到达到其中一个数组的末尾，这表示没有交集。如果在任何时候你有* A == * B - 这里是你的交集。
二进制匹配。在最坏情况下产生〜O（n * log（m））。你基本上选择较小的数组，并在较小阵列的所有元素的较大阵列中执行二进制搜索。如果你想变得更花哨，你甚至可以使用二分查找失败的最后位置，并将它用作下一个二分查找的起点。这样，你稍微改善最坏的情况，但对于一些集可能会执行奇迹:)
双重二进制匹配。它是普通二进制匹配的变体。基本上你可以从更小的阵列中获得元素，然后在更大的阵列中进行二进制搜索。如果你什么都没找到，那么你就把小数组缩小一半（是的，你可以折腾你已经使用过的元素），并将大数组减半（使用二分搜索失败点）。然后重复每对。结果比O（n * log（m））好，但我懒得计算它们是什么。

这些是最基本的两个。两者都有优点。线性实现起来更容易一些。二元期权的速度可以说比较快（尽管线性匹配的表现要比二元期权更好）。

如果有人知道比我想听到的更好的东西。匹配数组是我现在所做的。

P.S.不要引用我自己制作的“线性匹配”和“二进制匹配”这两个术语，而且可能已经有了一个奇特的名字。

来源

2011-01-05 05:28:41 Nazar

你已经弄明白了。 – nikhil 2012-06-25 16:20:38

奔驰搜索是去这里的正确途径，而不是你提到的任何事情。如果不匹配，则将指针指向较小的东西1，然后2，然后4，依次类推，直到检测到不匹配。然后在范围内进行二分法搜索，即可找到解决方案的括号。 – tmyklebu 2014-08-26 17:12:18

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

来源

2015-06-23 19:19:06 Kartik

让我们考虑两个排序数组： -

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

来源

2017-08-04 23:13:45

两个排序阵列的交集

回答

相关问题