Пересечение двух отсортированных массивов

Question

С учетом двух отсортированных массивов: A и B. Размер массива A равен La, а размер массива B равен Lb. Как найти пересечение A и B?

Если La намного больше, чем Lb, будет ли какая-либо разница для алгоритма поиска пересечения?

Answer 1

Так как это выглядит как 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

Answer 2

Некоторое время назад я боролся с той же проблемой, поэтому я пришел с:

1. Линейное сопоставление, которое в худшем случае даст O (m + n).Вы в основном сохраняете два указателя (A и B), каждый из которых указывает на начало каждого массива.Затем перемещайте указатель, который указывает на меньшее значение, пока вы не достигнете конца одного из массивов, который бы указывал на отсутствие пересечения.Если в какой-то момент у вас есть * A == * B - вот ваше пересечение.

2. Двоичное соответствие.Что дает ~ O (n * log (m)) в худшем случае.Вы в основном выбираете меньший массив и выполняете бинарный поиск в большем массиве всех элементов меньшего массива.Если вы хотите быть более навороченным, вы можете даже использовать последнюю позицию, где бинарный поиск не удался, и использовать ее в качестве отправной точки для следующего бинарного поиска.Таким образом, вы незначительно улучшаете худший случай, но для некоторых наборов он может творить чудеса:)

3. Двойное двоичное сопоставление.Это вариант обычного двоичного соответствия.В основном вы получаете элемент из середины меньшего массива и выполняете бинарный поиск в большем массиве.Если вы ничего не нашли, вы разрезаете меньший массив пополам (и да, вы можете отбросить элемент, который вы уже использовали) и разрезаете больший массив пополам (используйте точку сбоя двоичного поиска).А затем повторите для каждой пары.Результаты лучше, чем O (n * log (m)), но мне лень вычислять, что они собой представляют.

Это два самых основных из них.У обоих есть свои достоинства.Линейный немного проще в реализации.Двоичный вариант, возможно, быстрее (хотя существует множество случаев, когда линейное сопоставление будет превосходить двоичное).

Если кто-нибудь знает что-то лучше, я бы хотел услышать это.Совпадение массивов - это то, чем я занимаюсь в наши дни.

PS не цитируйте меня на терминах «линейное соответствие» и «бинарное соответствие», поскольку я сам их составил, и, вероятно, для него уже есть причудливое название.

Answer 3

Используйте set_intersection как здесь . Обычная реализация будет работать аналогично части слияния алгоритма сортировки слиянием.

Answer 4

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 5

Очень просто с PYTHON

Пример: А = [1,2,3,5,7,9,90] B = [2,4,10,90]

Вот три строки кода

for i in A:
     if(i in B):
        print(i)

Выход: 2, 90

Answer 6

Рассмотрим два отсортированных массива: -

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

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

Пока цикл будет работать, пока оба указателя не дойдут до соответствующей длины.

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

Answer 7

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