Przecięcie dwóch posortowanych tablic

Question

Otrzymano dwie posortowane tablice: A i B. Rozmiar tablicy A to La, a rozmiar tablicy B to Lb. Jak znaleźć skrzyżowanie A i B?

Jeśli La jest znacznie większy niż Lb, czy wystąpi jakakolwiek różnica dla algorytmu znajdującego się na skrzyżowaniu?

Answer 1

Użyj set_intersection jako . Zwykła implementacja będzie działać podobnie do scalonej części algorytmu scalania-sortowania.

Answer 2

Ponieważ wygląda jak HW ... Dam ci algorytmu:

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 3

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

Answer 4

mam zmaga się z tym samym problemem na chwilę teraz, tak dalece dołączonej:

1. Liniowe dopasowanie, które w najgorszym przypadku da O (m + n). Zasadniczo trzymaj dwa wskaźniki (A i B), z których każdy wskazuje początek każdej z tablic. Następnie przesuń wskaźnik, który wskazuje na mniejszą wartość, aż dotrzesz do końca jednej z tablic, co wskazywałoby na brak przecięcia. Jeśli w którymkolwiek momencie masz * A == * B - oto twoje skrzyżowanie.

2. Dopasowanie binarne. Który daje ~ O (n * log (m)) w najgorszym przypadku. Zasadniczo wybierasz mniejszą tablicę i wykonujesz wyszukiwanie binarne w większej tablicy wszystkich elementów mniejszej tablicy. Jeśli chcesz mieć więcej ochoty, możesz nawet użyć ostatniej pozycji, w której nie powiodło się wyszukiwanie binarne i użyć jej jako punktu początkowego do następnego wyszukiwania binarnego. W ten sposób marginalnie poprawisz najgorszy przypadek, ale dla niektórych zestawów może on dokonać cudów :)

3. Podwójne dopasowanie binarne. Jest to odmiana zwykłego dopasowywania binarnego. Zasadniczo dostajesz element ze środka mniejszej tablicy i wykonujesz wyszukiwanie binarne w większej tablicy. Jeśli nic nie znajdujesz, przecinasz mniejszą tablicę na pół (i tak możesz wrzucić element, który już używałeś) i wyciąć większą tablicę na pół (użyj punktu niepowodzenia wyszukiwania binarnego). A następnie powtórz dla każdej pary. Wyniki są lepsze niż O (n * log (m)), ale jestem zbyt leniwy, aby obliczyć, jakie one są.

Są to dwie najbardziej podstawowe z nich. Oba mają zalety. Linear jest nieco łatwiejszy w implementacji. Wersja binarna jest prawdopodobnie szybsza (chociaż istnieje wiele przypadków, w których dopasowanie liniowe przewyższy wydajność binarną).

Jeśli ktoś wie coś lepszego niż to, chciałbym to usłyszeć. Dopasowywanie tablic jest tym, co robię obecnie.

P.S. nie cytujcie mnie na warunkach "dopasowywania liniowego" i "dopasowywania binarnego", ponieważ sam je tworzyłem i prawdopodobnie już jest to wymyślna nazwa.

Answer 5

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

Answer 6

Rozważmy dwa posortowane tablice: -

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

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

Podczas gdy pętla będzie działać aż oba wskaźniki dotrzeć do odpowiednich długościach.

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

wyjściowe będą: -

2 4 8