Тестирование, если несортированные множества не пересекаются в линейном времени.(домашнее задание)

Question

Проблема: Два набора A и B имеют n элементов каждый. Предположим, что каждый элемент является целым числом в диапазоне [0, n ^ 100]. Эти наборы не обязательно отсортированы. Покажите, как проверить, не пересекаются ли эти два набора в O (n) времени. Ваш алгоритм должен использовать O (n) пробел.

Моя первоначальная идея для этой проблемы состояла в том, чтобы создать хеш-таблицу набора A и выполнить поиск в этой хеш-таблице для каждого элемента в B. Однако я не знаю ни одного способа создания хеш-таблицы набора данных с этим диапазоном, который занимает только O (n) пространство. Должен ли я рассмотреть совершенно другой подход?

UPDATE: Я связался с профессором по поводу этой проблемы с вопросом о реализации хэш-таблицы, и он ответил: Обратите внимание, что хеширование занимает в среднем O (1) времени для операций. Для этой задачи нам понадобится алгоритм времени O (n) в худшем случае.

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

Answer 1

Ввод: Массивы A [м], B [n]

Вывод: True, если они не пересекаются, False в противном случае

---

1. Грубая сила: O (м * n) время, O (1) пробел

1. Search for each element of A into B
2. As soon as you get a match break and return false
3. If you reach till end, return true

Преимущество: Не изменяет ввод

---

2. Сортировать оба O (mlogm + nlogn + m + n)

1. Sort both arrays
2. Scan linearly

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

---

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

1. Say, m < n, sort A
2. Binary search for each element of B into A

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

---

4. Сортировать больше O ((m + n) logn)

1. Say n > m, sort B
2. Binary search for each element of A into B

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

---

5. Хеширование O (м + n) времени, O (м) или O (n) пробела

Преимущество: Не изменяет ввод

Answer 2

Почему бы не использовать хеш-таблицу?Разве они не O (n) для создания (при условии, что все они уникальны), тогда O (n) для поиска, будучи O (2n) = O (n)?

Answer 3

Хэш-набор будет работать нормально. Чрезвычайно распространено предположение, что хэш-наборы / таблицы имеют постоянное время для каждой операции, хотя это не совсем так.

Обратите внимание, что в хэш-наборах / таблицах абсолютно используется только пространство, пропорциональное вставленным элементам, а не потенциальное общее количество элементов. Вы, кажется, неправильно поняли это.

Если «по общему мнению, это достаточно хорошо» по какой-то причине неприемлемо, вы можете использовать основную сортировку. Это линейно в общем размере представления входных элементов. (Предостережение: это немного отличается от того, чтобы быть линейным по количеству элементов.)