Найти общие элементы в двух массивах в сложность линейного времени

Question

Я знаю, что этот тип вопросов повторялся в сообществе, но мой вопрос немного отличается от других.

Сегодня я столкнулся с опросом известной компании. Они задали мне два технических вопроса: один из вопросов был ...

Я дал два несортированных массива длины n, они попросили меня найти общие элементы массивов, но с алгоритмом временной сложности O (n) ,

Нет дополнительной поддержки, связанной с языком.

Я показал им алгоритм со сложностью времени O (n * log (n)), но они не были удовлетворены. Я просто хочу знать Если существует какой-либо алгоритм такого рода.

Answer 1

Вы можете использовать хэш-карту для хранения всех элементов первого массива (вместе со своим счетчиком для обработки повторяющихся элементов).

Затем пройдите 2-й массив и проверьте, присутствуют ли они в хэш-карте. Идеальная временная сложность будет O(2n). Так как элемент & извлекается из него в O (1) раз.

Вы достигаете временной сложности O (n), но ваш space complexity также становится O (n).

Answer 2

Вы можете использовать HashSet (в C++ это будет unordered_multiset), чтобы сохранить элементы первого массива, а затем итерации по второму найти те, которые существуют в HashTable. Поскольку доступ к элементу в среднем имеет постоянную временную сложность, этот алгоритм будет работать в O (n).

Answer 3

С помощью комментариев и других ответов я пришел к тому, что не существует никакой возможности сделать это в O (N) без использования HashMap в C++ или набор в Python (Что на самом деле поддержка языка и также увеличивает космическую сложность).

Итак, вот решение в питоне:

list1 = [4,2,5,7,1] 
list2 = [8,2,4,1,6] 

ans = list(set(list1) & set(list2)) 
print 'Common Elements: ',ans 

>>> Common Elements: [1, 2, 4]