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

Question

Практика для интервью разработчиков программного обеспечения и застрял на вопрос алгоритма.

Given two sets of unsorted integers with array of length m and other of 
length n and where m < n find an efficient algorithm to determine if 
the sets are disjoint. I've found solutions in O(nm) time, but haven't 
found any that are more efficient than this, such as in O(n log m) time.

Answer 1

Используя структуру данных с O(1) поиском / вставкой, вы можете легко вставить все элементы первого набора.

Тогда элемент foreach во втором наборе, если он существует, не является дизъюнктным, в противном случае он не дизъюнктен

ПСЕВДОКОД

function isDisjoint(list1, list2)
    HashMap = new HashMap();
    foreach( x in list1)
        HashMap.put(x, true);

    foreach(y in list2)
        if(HashMap.hasKey(y))
             return false;
    return true;

Это даст вам решение O(n + m)

Answer 2

Довольно очевидный подход - отсортировать массив по длине m - O(m log m), Для каждого элемента в массиве длины n, используйте бинарный поиск, чтобы проверить, существует ли он в массиве длины m - O(log m) за элемент = O(n log m), поскольку m<nэто составляет O(n log m),

Answer 3

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

Как я уже говорил, это работает, потому что хеш-таблица дает постоянное время поиска в среднем случае. В редком случае, когда много уникальных элементов в m иметь такой же хэш, это займет немного больше времени. Однако большинству людей не нужно заботиться о гипотетических худших случаях. Например, быстрая сортировка используется больше, чем сортировка слиянием, потому что она дает лучшую среднюю производительность, несмотря на O(n^2) верхняя граница.

Answer 4

Вот ссылка на пост, который, я думаю, отвечает на ваш вопрос.

3) Сортировать меньше O((m + n)logm)

1. Скажем, m
2. Бинарный поиск для каждого элемента B в A

Недостаток: изменяет ввод