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

Ответ 1

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

Ответ 2

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

Ответ 3

Я некоторое время боролся с той же проблемой, пока я пришел с:

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

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

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

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

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

P.S. не цитируйте меня на терминах "линейное соответствие" и "бинарное сопоставление", поскольку я сам их создал, и, вероятно, для этого уже есть фантастическое имя.

Ответ 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;
}

Ответ 5

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

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

Ответ 6

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