Accounts Merge

Средняя№721

Дан список аккаунтов: в каждом имя, а за ним email. Два аккаунта принадлежат одному человеку, если у них есть общий email, в том числе через другие аккаунты; одно имя ещё не значит один человек. Нужно слить аккаунты каждого человека и вернуть его как имя и все его email по порядку. Наш пример: ["Ann", "ann@home", "ann@work"], ["Ann", "a.k@uni", "ann@work"], ["Ann", "ak@mail", "a.k@uni"], ["Ann", "ann@x"] → ["Ann", "a.k@uni", "ak@mail", "ann@home", "ann@work"], ["Ann", "ann@x"].

721 Accounts MergeРазбор · 1×

Пример: ["Ann", "ann@home", "ann@work"], ["Ann", "a.k@uni", "ann@work"], ["Ann", "ak@mail", "a.k@uni"], ["Ann", "ann@x"]. Все четыре — Ann. Аккаунт 2 делит a.k@uni с аккаунтом 1, а аккаунт 1 делит ann@work с аккаунтом 0, поэтому все трое — один человек; у аккаунта 3 общего ничего нет.

012300112233parentownergroups—
смотрим сейчаскорень группы аккаунтов

Каждый из 4 аккаунтов — сам себе корень

01/75
сначала · назад · пуск · шаг
Скорость
1function accountsMerge(accounts):
2 parent = [0, 1, ..., n - 1]
3 owner = empty map // email → first account with it
4 for each account i and each email of it:
5 if email not in owner:
6 owner[email] = i
7 else:
8 rootO = find(owner[email])
9 rootI = find(i)
10 if rootO is not rootI:
11 parent[rootI] = rootO
12 groups = empty map // root → set of emails
13 for i from 0 to n - 1:
14 root = find(i)
15 add emails of accounts[i] to groups[root]
16 return [name, sorted emails] for each group
17
18function find(x):
19 while parent[x] is not x:
20 x = parent[x]
21 return x
состояние
parent
[0, 1, 2, 3]
i
–
email
–
rootO
–
rootI
–
root
–
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Элементы Union-Find — аккаунты. owner хранит первый аккаунт каждого email, поэтому повторный email связывает аккаунт с тем первым, а связи не рвутся.
  2. Связь переходит дальше: аккаунт 2 встречает аккаунт 1, который уже под аккаунтом 0, и все трое оказываются под одним корнем, хотя аккаунт 2 с аккаунтом 0 не встречался.
  3. Группировка по корню аккаунта собирает все email человека в одном месте; множество убирает повторы, а из аккаунта берём только имя.

Сложность

Время O(E · h + E log E) для E email всего: до двух find на email глубиной с дерево (здесь до числа аккаунтов, почти константа, если перевешивать на корень и подвешивать меньшее дерево под большее), плюс сортировка. Память O(E) на owner и groups.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.