Как найти повторяющиеся элементы в разных коллекциях за линейное время?

Question

[Андрей Кулагин]

Подскажите плиз с алгоритмом решения задачи, я представляю, что нужно сделать HashMap, ключ будет user, значение список имейлов(я могу их добавлять в hashset например), как потом находить в разных коллекциях повторяющиеся элементы за линейное время?

Имеется n пользователей, каждому из них соответствует список email-ов
(всего у всех пользователей m email-ов).
Например:
user1 ->[e-mail],[e-mail],[e-mail] ([e-mail],[e-mail],[e-mail])
user2 ->[e-mail],[e-mail] ([e-mail],[e-mail])
user3 ->[e-mail],[e-mail] ([e-mail],[e-mail])
user4 ->[e-mail],[e-mail] ([e-mail],[e-mail])
user5 ->[e-mail]
Считается, что если у двух пользователей есть общий email, значит это
один и тот же пользователь. Требуется построить
и реализовать алгоритм, выполняющий слияние пользователей. На выходе
должен быть список пользователей с их email-ами (такой же как на
входе).
В качестве имени объединенного пользователя можно брать любое из
исходных имен. Список email-ов пользователя должен содержать только
уникальные email-ы.
Параметры n и m произвольные, длина конкретного списка email-ов никак
не ограничена.
Требуется, чтобы асимптотическое время работы полученного решения было
линейным, или близким к линейному.

Answer 1

[Wataru]

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

Перенумеруйте все емейлы и всех пользователей.
Код будет проще, если емейлы и пользователи хранятся в одном и том же пространстве номеров.
Это реализуется с одним hashMap, который будет давать номер по строке, и одним массивом строк, который будет хранить изначальную строку по номеру. Вам еще понадобится булевый массив, чтобы хранить, является ли данная вершина пользователем или мейлом. При вводе получаете какую-то строку, и вызываете от нее функцию GetID(s, is_user), которая проверяет, есть ли данная строка в мапе. Если есть, возвращает номер. Если нет - дописывает строку в массив строк, записывает ее индекс в мап и возвращает его.

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

Заведите массив пометок "обойденности" для всех вершин. Он будет int. 0 - непосещенные вершины, иначе номер компоненты связности.
Запустите на этом графе DFS/BFS от каждой пока не обойденной вершины в цикле и помечайте все достижимые вершины новым числом (можно передавать вторым параметром в DFS). Можно сразу же во время обхода заполнять структуру ответ - один номер для пользователя и список для емейлов. Или можно после цикла с DFS завести массив списков для ответа, пройтись по массиву и распихать номера вершин по спискам. Используйте булевый массив, чтобы понять какая вершина пользователь, а какая - мейл. Из пользователей возьмите только одного предстваителя, а все емейлы запихайте в список в ответ. Потом выводите, преобразуя номера в строки с помощью имеющегося массива.

Comments

[Андрей Кулагин]

спасибо, попробую разобраться

Answer 2

[Сергей Тихонов]

По-моему построить обратный индекс "email - список пользователей" как раз будет занимать линейное время (если вставка в хешмап линейна), по дороге можно отмечать те мейлы, в которых в списке более одного элемента оказалось.

Comments

[Андрей Кулагин]

В Hashmap добавляю ключ - это коллекция hashset, состоящая из уникальных имейлов, а значение это user
А дальше что с этим делать?

[Сергей Тихонов]

Значение - список пользователей. Если там больше чем один пользователь, можно начинать клеить: для этого нужна карта пользователь - пользователь

[Андрей Кулагин]

Сергей Тихонов, а как тогда проверить что имейлы повторяются в разных списках?

[Алексей Черемисин]

Делаете хеш, ключем емейл, значением - массив id пользователей.
Вторым проходом фильтруете это хеш, если размер массива в ключе больше 1

[Андрей Кулагин]

спасибо!