Giao điểm của hai mảng được sắp xếp

Question

Cho hai mảng được sắp xếp: A và B. Kích thước của mảng A là La và kích thước của mảng B là Lb. Cách tìm giao lộ của A và B?

Nếu La lớn hơn nhiều so với Lb, thì sẽ có bất kỳ sự khác biệt nào đối với thuật toán tìm giao lộ không?

Answer 1

Sử dụng set_intersection làm here. Việc thực hiện thông thường sẽ hoạt động tương tự như phần hợp nhất của thuật toán sắp xếp hợp nhất.

Answer 2

Vì đây trông giống như một HW ... Tôi sẽ cung cấp cho bạn các thuật toán:

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

Tôi đã đấu tranh với cùng một vấn đề trong một thời gian bây giờ, cho đến nay tôi đi kèm với:

1. Đối sánh tuyến tính sẽ mang lại O (m + n) trong trường hợp xấu nhất. Bạn về cơ bản giữ hai con trỏ (A và B) mỗi trỏ đến đầu của mỗi mảng. Sau đó, trước con trỏ trỏ đến giá trị nhỏ hơn, cho đến khi bạn kết thúc một trong các mảng, điều đó sẽ cho biết không có giao lộ. Nếu tại bất kỳ thời điểm nào bạn có * A == * B - ở đây có giao lộ của bạn.

2. Kết hợp nhị phân. Mà sản lượng ~ O (n * log (m)) trong trường hợp xấu nhất. Về cơ bản bạn chọn mảng nhỏ hơn và thực hiện tìm kiếm nhị phân trong mảng lớn hơn của tất cả các phần tử của mảng nhỏ hơn. Nếu bạn muốn được ưa thích hơn, bạn thậm chí có thể sử dụng vị trí cuối cùng mà tìm kiếm nhị phân thất bại và sử dụng nó như là điểm khởi đầu cho tìm kiếm nhị phân tiếp theo. Bằng cách này bạn cải thiện nhẹ trường hợp xấu nhất nhưng đối với một số bộ nó có thể thực hiện phép lạ :)

3. Kết hợp nhị phân kép. Đó là một biến thể của kết hợp nhị phân thông thường. Về cơ bản bạn nhận được phần tử từ giữa mảng nhỏ hơn và tìm kiếm nhị phân trong mảng lớn hơn. Nếu bạn không tìm thấy gì thì bạn cắt mảng nhỏ hơn một nửa (và có bạn có thể quăng phần tử bạn đã sử dụng) và cắt mảng lớn hơn một nửa (sử dụng điểm thất bại tìm kiếm nhị phân). Và sau đó lặp lại cho mỗi cặp. Kết quả tốt hơn O (n * log (m)) nhưng tôi quá lười để tính toán chúng là gì.

Đó là hai loại cơ bản nhất. Cả hai đều có giá trị. Tuyến tính dễ triển khai hơn một chút. Nhị phân được cho là nhanh hơn (mặc dù có rất nhiều trường hợp khi khớp tuyến tính sẽ hoạt động tốt hơn nhị phân).

Nếu có ai biết điều gì tốt hơn tôi rất muốn nghe. Mảng phù hợp là những gì tôi làm những ngày này.

P.S. không báo cho tôi về các thuật ngữ "khớp tuyến tính" và "kết hợp nhị phân" khi tôi tự tạo chúng và có lẽ là tên lạ mắt cho nó.

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

Hãy xem xét hai mảng được sắp xếp: -

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

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

Trong khi vòng lặp sẽ chạy cho đến khi cả hai con trỏ lên tới độ dài tương ứng.

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 sẽ là: -

2 4 8