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

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

Может кто- то подсказать, делаю задачу , где нужно объединить пользователей с общим имейл,
с помощью двух hashmap, сделал одну, где ключ- имейл пользователя, а значение имя юзера, но там же значения перезатираются с общим ключом, что я делаю не так?
Имеется n пользователей, каждому из них соответствует список email-ов
(всего у всех пользователей m email-ов).
Например:
user1 ->xxx@ya.ru,foo@gmail.com,lol@mail.ru (xxx@ya.ru,foo@gmail.com,lol@mail.ru)
user2 ->foo@gmail.com,ups@pisem.net (foo@gmail.com,ups@pisem.net)
user3 ->xyz@pisem.net,vasya@pupkin.com (xyz@pisem.net,vasya@pupkin.com)
user4 ->ups@pisem.net,aaa@bbb.ru (ups@pisem.net,aaa@bbb.ru)
user5 ->xyz@pisem.net
Считается, что если у двух пользователей есть общий email, значит это
один и тот же пользователь. Требуется построить
и реализовать алгоритм, выполняющий слияние пользователей. На выходе
должен быть список пользователей с их email-ами (такой же как на
входе).
В качестве имени объединенного пользователя можно брать любое из
исходных имен. Список email-ов пользователя должен содержать только
уникальные email-ы.
Параметры n и m произвольные, длина конкретного списка email-ов никак
не ограничена.
Требуется, чтобы асимптотическое время работы полученного решения было
линейным, или близким к линейному.
Возможный ответ на задачу в указанном примере:
user1 ->xxx@ya.ru,foo@gmail.com,lol@mail.ru,ups@pisem.net,aaa@bbb.ru (xxx@ya.ru,foo@gmail.com,lol@mail.ru,ups@pisem.net,aaa@bbb.ru)
user3 ->xyz@pisem.net,vasya@pupkin.com (xyz@pisem.net,vasya@pupkin.com)

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:xxx@ya.ru,foo@gmail.com,lol@mail.ru"),
new User("user2:foo@gmail.com,ups@pisem.net"),
new User("user3:xyz@pisem.net,vasya@pupkin.com"),
new User("user4:ups@pisem.net,aaa@bbb.ru"),
new User("user5:xyz@pisem.net")
);
email.convert(source);
}
}

Выводит вот это:
aaa@bbb.ru user4
ups@pisem.net user4
lol@mail.ru user1
xxx@ya.ru user1
vasya@pupkin.com user3
foo@gmail.com user2
xyz@pisem.net user5
  • Вопрос задан
  • 233 просмотра
Ответы на вопрос 2
LaRN
@LaRN
Senior Developer
Можно вот так попробовать.
В первом 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 принадлежат одному юзеру.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вы уже задавали этот вопрос.

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

Вопрос закрыт для ответов и комментариев

Потому что уже есть похожий вопрос.
Похожие вопросы