Алгоритм для поиска, если два набора пересекаются

Скажем, у меня есть два массива:

int ArrayA [] = {5, 17, 150, 230, 285};

int ArrayB [] = {7, 11, 57, 110, 230, 250};

Оба массива сортируются и могут быть любого размера. Я ищу эффективный алгоритм для поиска, если массивы содержат любые дублированные элементы между ними. Мне просто нужен истинный/ложный ответ, мне все равно, какой элемент является общим или сколько.

Наивное решение состоит в том, чтобы перебирать каждый элемент в ArrayA и выполнять двоичный поиск для него в ArrayB. Я считаю, что эта сложность - O (m * log n).

Поскольку оба массива отсортированы, кажется, что должен быть более эффективный алгоритм.

Мне также хотелось бы получить общее решение, которое не предполагает, что массивы содержат числа (т.е. решение должно также работать для строк). Однако операторы сравнения хорошо определены и оба массива отсортированы от наименьшего к наибольшему.

Ответы

Ответ 1

Представьте, что вы делаете слияние, но не отправляете результаты нигде. Если вы дойдете до конца любого источника, пересечения не будет. Каждый раз, когда вы сравниваете следующий элемент каждого из них, если они равны, есть пересечение.

Например:

counterA = 0;
counterB = 0;
for(;;) {
    if(counterA == ArrayA.length || counterB == ArrayB.length)
        return false;
    else if(ArrayA[counterA] == ArrayB[counterB])
        return true;
    else if(ArrayA[counterA] < ArrayB[counterB])
        counterA++;
    else if(ArrayA[counterA] > ArrayB[counterB])
        counterB++;
    else
        halt_and_catch_fire();
}

Ответ 2

Так как кто-то задавался вопросом о stl. Из-за коробки алгоритм set_intersection будет делать больше, чем вы хотите: он найдет все общие значения.

    #include <vector>
    #include <algorithm>
    #include <iterator>
    using namespace std;
//    ...    
      int ArrayA[] = {5, 17, 150, 230, 285};
      int ArrayB[] = {7, 11, 57, 110, 230, 250};
      vector<int> intersection;
      ThrowWhenWritten output_iterator;
        set_intersection(ArrayA, ArrayA + sizeof(ArrayA)/sizeof(int),
                         ArrayB, ArrayB + sizeof(ArrayB)/sizeof(int),
                         back_insert_iterator<vector<int> >(intersection));

        return !intersection.empty();

это выполняется в O (m + n) времени, но требует хранения всех дубликатов и не останавливается, когда находит первый dup.

Теперь, изменив код из gnu реализация в stl, мы можем получить более точное, что вы хотите.

 template<typename InputIterator1, typename InputIterator2>
 bool 
 has_intersection(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, InputIterator2 last2)
    {
       while (first1 != last1 && first2 != last2) 
       {
          if (*first1 < *first2)
             ++first1;
          else if (*first2 < *first1)
             ++first2;
          else
             return true;
       }
       return false;
}

Ответ 3

Если один список намного короче другого, двоичный поиск - это путь. Если списки имеют одинаковую длину, и вы довольны O (m + n), будет работать стандартное "слияние". Есть более привлекательные алгоритмы, которые являются более гибкими. Одна статья, с которой я столкнулся в своих собственных поисках, это:

http://www.cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf

Ответ 4

Если вы не заботитесь о потреблении памяти, вы можете добиться хорошей производительности с помощью хэша, т.е. создать хеш с ключами = значения одного массива и проверить значения второго массива против этого хэша

Ответ 5

Если вы используете С# 3.0, то почему бы вам не воспользоваться LINQ здесь?

ArrayA.Intersect(ArrayB).Any()

Не только этот общий (работает для любого сопоставимого типа) реализация под капотом довольно эффективна (использует алгоритм хеширования).

Ответ 6

Если диапазон значений мал, вы можете построить таблицу поиска для одного из них (time cost = O (N)), а затем проверить, установлен ли бит из другого списка (временная стоимость = O (N)). Если диапазон большой, вы можете сделать что-то подобное с хэш-таблицей.

Слияние с Glomek - еще лучшая идея.

Ответ 7

Glomek находится на правильном пути, но затушевывает алгоритм.

Начните с сравнения ArrayA [0] с ArrayB [0]. если они равны, все готово. Если ArrayA [0] меньше ArrayB [0], перейдите к ArrayA [1]. Если ArrayA [0] больше ArrayB [0], перейдите в ArrayB [1].

Сохраняйте шаг вперед, пока не достигнете конца одного массива или найдите совпадение.