Как объеденить пользователей с общим имейл?

Question

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

Может кто- то подсказать, делаю задачу , где нужно объединить пользователей с общим имейл,
с помощью двух hashmap, сделал одну, где ключ- имейл пользователя, а значение имя юзера, но там же значения перезатираются с общим ключом, что я делаю не так?
Имеется 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-ов никак
не ограничена.
Требуется, чтобы асимптотическое время работы полученного решения было
линейным, или близким к линейному.
Возможный ответ на задачу в указанном примере:
user1 ->[e-mail],[e-mail],[e-mail],[e-mail],[e-mail] ([e-mail],[e-mail],[e-mail],[e-mail],[e-mail])
user3 ->[e-mail],[e-mail] ([e-mail],[e-mail])

public class Email implements Sort {
public void convert(List source) {
Map map1 = new HashMap<>();
Map map2 = new HashMap<>();
for (int i = 0; i < source.size(); i++) {
String[] list1 = source.get(i).getUser().split(":");
String[] list2 = list1[1].split(",");
for (int j = 0; j < list2.length; j++) {
//ключ- имейл пользователя
String key = list2[j];
//значение - имя юзера
String value = list1[0];
map1.put(key, value);
}
}

for (String key : map1.keySet()) {
System.out.println(key + " " + map1.get(key));
}
}

public static void main(String[] args) {
Email email = new Email();
List source = Arrays.asList(
new User("user1:[e-mail],[e-mail],[e-mail]"),
new User("user2:[e-mail],[e-mail]"),
new User("user3:[e-mail],[e-mail]"),
new User("user4:[e-mail],[e-mail]"),
new User("user5:[e-mail]")
);
email.convert(source);
}
}

Выводит вот это:
[e-mail] user4
[e-mail] user4
[e-mail] user1
[e-mail] user1
[e-mail] user3
[e-mail] user2
[e-mail] user5

Answer 1

[Руслан .]

Можно вот так попробовать.
В первом hashmap можно хранить пару mail-user, во втором hashmap пару user - user.
Пример:
u1-m1, m2
u2-m3, m2
u3-m4
u5-m4, m5, m1

Идём по списку, обрабатывает пару u1-m1.
m1-u1 -> heshmap1
Дальше аналогично для второй пары:
m2-u1 -> heshmap1
Для следующей пары:
m3-u2 -> heshmap1
Следующая пара, тут важный момент, т.к. ключ
m2 уже есть в heshmap1, то не нужно туда ничего писать, а нужно добавить в
heshmap2 для ключа u2 значение u1, потому что в heshmap1 значение для ключа m2 есть u1.
Т.е. имеем u2-u1 -> heshmap2
Далее
m4-u3 -> heshmap1
Затем, т.к. ключ m4 уже есть в heshmap1 снова идём в heshmap2:
u5-u3 -> heshmap2
Далее
m5-u5-> heshmap1
И последний шаг u5 - m1, тут нюанс, в heshmap1
уже есть ключ m1 значит идём в heshmap2, но там тоже уже есть ключ u5, значит нужно уже имеющуюся в heshmap2 пару u5-u3 удалить и вместо неё добавить две новые:
u3-u1-> hashmap2
u5-u1-> hashmap2
Значение u1 берём из hashmap1[m1]

В итоге имеем:
heshmap1
m1-u1
m2-u1
m3-u2
m4-u3
m5-u5
heshmap2
u2-u1
u3-u1
u5-u1
Далее идём по ключам heshmap1(это email) и определяем для каждого из них значение из heshmap2 (это пользователи).
mail = heshmap1[heshmap1.key[i]]
user = heshmap2[heshmap1[mail]]
Если в heshmap2 нет какого-то значения, значит берём юзера из heshmap1.key[i]

В итоге соединив два heshmap получим такой список:
u1-m1
u1-m2
u1-m3
u1-m4
u1-m5
Т.е. все email принадлежат одному юзеру.

Answer 2

[Wataru]

Вы уже задавали этот вопрос.

Я там вам ответил, что это класическая задача на нахождение компонет связности в графе. Гуглите DFS, компоненты связности, графы. Я там даже технических деталей кучу привел.

Comments

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

сейчас другое условие, делать с помощью двух hashmap

[Wataru]

Андрей Шалыгин, Прям вам в условии и сказано, что должно быть 2 hashmap'a? Если так надо, вы можете использовать их для храниния ребер в графе - для каждого пользоватля выдавать список емейлов и наоборот. Еще нужно будет как-то хранить пометки обойденных вершин. Это еще один хешмап. Если нужно ровно 2 - то один для ребер, второй для пометок.

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

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

wataru, без графов сказали делать

[Wataru]

Какой изврат. Любое решение этой задачи будет так или иначе работать с графом. Возможно неявно.

Вы не называйте граф - графом, и будет без графов)

Один хешмап будет по пользователю выдававть список емейлов. Второй - по емейлу список пользователей. Третий - по пользователю или емейлу выдавать выведен ли этот пользователь уже или нет.

Заполните мапы, потом пройдитесь по всем пользователем, и если он еще не выведен, пишите в ответ его логин и запускайте рекурсивную функцию GetAllMails(user). Она первым делом помечает пользователя как выведенного, проходится по списку его имейлов, и если они еще не выведены, выводит их и помечает выведенными. Для каждого добавленного имейла надо вложенным циклом пройтись по списку пользователей. Если пользователь еще не выведен - запуститься рекурсивно.

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

Тут видно, что работает за линейную сложность - GetAllMails может запуститься только один раз от каждого пользователя. Внутри оно один раз проходит список его емейлов. Для каждого емейла ровно один раз, при выводе, будет пройден список всех пользователей с таким мылом.