721. 账户合并
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回
示例 1
输入：accounts = [[“John”, “johnsmith@mail.com“, “john00@mail.com“], [“John”, “johnnybravo@mail.com“], [“John”, “johnsmith@mail.com“, “john_newyork@mail.com“], [“Mary”, “mary@mail.com“]]
输出：[[“John”, ‘john00@mail.com‘, ‘john_newyork@mail.com‘, ‘johnsmith@mail.com‘], [“John”, “johnnybravo@mail.com“], [“Mary”, “mary@mail.com“]]
解释：第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com“。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [[‘Mary’，‘mary@mail.com‘]，[‘John’，‘johnnybravo@mail.com‘]，
[‘John’，‘john00@mail.com‘，‘john_newyork@mail.com‘，‘johnsmith@mail.com‘]] 也是正确的
示例 2
输入：accounts = [[“Gabe”,”Gabe0@m.co“,”Gabe3@m.co“,”Gabe1@m.co“],[“Kevin”,”Kevin3@m.co“,”Kevin5@m.co“,”Kevin0@m.co“],[“Ethan”,”Ethan5@m.co“,”Ethan4@m.co“,”Ethan0@m.co“],[“Hanzo”,”Hanzo3@m.co“,”Hanzo1@m.co“,”Hanzo0@m.co“],[“Fern”,”Fern5@m.co“,”Fern1@m.co“,”Fern0@m.co“]]
输出：[[“Ethan”,”Ethan0@m.co“,”Ethan4@m.co“,”Ethan5@m.co“],[“Gabe”,”Gabe0@m.co“,”Gabe1@m.co“,”Gabe3@m.co“],[“Hanzo”,”Hanzo0@m.co“,”Hanzo1@m.co“,”Hanzo3@m.co“],[“Kevin”,”Kevin0@m.co“,”Kevin3@m.co“,”Kevin5@m.co“],[“Fern”,”Fern0@m.co“,”Fern1@m.co“,”Fern5@m.co“]]
提示
邮箱相同，用户就相同
Solution 1
第一次尝试，通过深度优先搜索解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Set<String> existEmails = new HashSet<>();
Set<Integer> existIdxs = new HashSet<>();
List<List<String>> merged = new ArrayList<>();
List<String> temp;
for (List<String> ignored : accounts) {
temp = new ArrayList<>();
dfs(existEmails, existIdxs, temp, accounts);
if (!temp.isEmpty()) {
if (temp.size() > 2) {
Set<String> emailSet = new HashSet<>(temp.subList(1, temp.size()));
List<String> emails = new ArrayList<>(emailSet);
Collections.sort(emails);
List<String> list = new ArrayList<>();
list.add(temp.get(0));
list.addAll(emails);
merged.add(list);
} else {
merged.add(temp);
}
}
}
return merged;
}
private void dfs(Set<String> existEmails,
Set<Integer> existIdxs,
List<String> temp,
List<List<String>> accounts) {
for (int i = 0, k = accounts.size(); i < k; i++) {
if (!existIdxs.contains(i)) {
List<String> emails = accounts.get(i).subList(1, accounts.get(i).size());
if (temp.isEmpty()) {
temp.addAll(accounts.get(i));
existIdxs.add(i);
existEmails.addAll(emails);
} else {
boolean merged = false;
for (String email : emails) {
if (existEmails.contains(email)) {
merged = true;
break;
}
}
if (merged) {
existIdxs.add(i);
existEmails.addAll(emails);
temp.addAll(emails);
dfs(existEmails, existIdxs, temp, accounts);
}
}
}
}
}
}
|
- 执行用时：469 ms（击败 6.28% 使用 Java 的用户）
- 内存消耗：50.55 MB（击败 5.00% 使用 Java 的用户）
Solution 2
推荐解法，通过 并查集 解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, Integer> email2Index = new HashMap<>();
Map<String, String> email2Name = new HashMap<>();
int emailIdx = 0;
int count = 0;
for (List<String> account : accounts) {
String name = account.get(0);
count = account.size();
for (int i = 1; i < count; i++) {
String email = account.get(i);
if (!email2Index.containsKey(email)) {
email2Index.put(email, emailIdx++);
email2Name.put(email, name);
}
}
}
UnionFind uf = new UnionFind(emailIdx);
for (List<String> account : accounts) {
String firstEmail = account.get(1);
int firstIdx = email2Index.get(firstEmail);
for (int i = 2, k = account.size(); i < k; i++) {
String nextEmail = account.get(i);
int nextIdx = email2Index.get(nextEmail);
uf.union(firstIdx, nextIdx);
}
}
Map<Integer, List<String>> emailIdxMap = new HashMap<>();
email2Index.forEach((k, v) -> {
int rootIdx = uf.find(v);
List<String> emails = emailIdxMap.getOrDefault(rootIdx, new ArrayList<>());
emails.add(k);
emailIdxMap.put(rootIdx, emails);
});
List<List<String>> merged = new ArrayList<>();
List<String> val;
for (List<String> emails : emailIdxMap.values()) {
Collections.sort(emails);
String name = email2Name.get(emails.get(0));
val = new ArrayList<>();
val.add(name);
val.addAll(emails);
merged.add(val);
}
return merged;
}
private static class UnionFind {
int[] node;
public UnionFind(int size) {
node = new int[size];
for (int i = 0; i < size; i++) {
node[i] = i;
}
}
public void union(int index1, int index2) {
node[find(index2)] = find(index1);
}
public int find(int index) {
if (node[index] != index) {
node[index] = find(node[index]);
}
return node[index];
}
}
}
|
- 执行用时：28 ms（击败 94.76% 使用 Java 的用户）
- 内存消耗：47.93 MB（击败 32.94% 使用 Java 的用户）
Source
721. 账户合并 - 力扣（LeetCode）
