兩個排序陣列的交集

給定兩個排序陣列：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

兩個排序陣列的交集

回答

相關問題