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

Question

Допустим, у меня есть два массива:

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

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

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

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

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

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

Answer 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();
}

Answer 2

Так как кто-то задумался о стл. Встроенный алгоритм 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), но требует сохранения всех дубликатов и не останавливается, когда находит первый дубликат.

Теперь, изменив код из реализации 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;
}

Answer 3

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

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

Answer 4

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

Answer 5

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

ArrayA.Intersect(ArrayB).Any()

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

Answer 6

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

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

Продолжайте шагать, пока не дойдете до конца одного массива или не найдете совпадение.

Answer 7

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

Трюк слияния от Glomek - еще лучшая идея.