友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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"]
]
提示：
-
1 <= accounts.length <= 1000 -
2 <= accounts[i].length <= 10 -
1 <= accounts[i][j].length <= 30 -
accounts[i][0]由英文字母组成 -
accounts[i][j] (for j > 0)是有效的邮箱地址
思路分析
并查集。
通过邮箱编号建立连接，而不是通过账户索引建立连接。
也可以使用深度优先遍历。
-
一刷
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
76
77
78
79
80
81
82
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-21 21:49:58
*/
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, Integer> emailToNoMap = new HashMap<>();
Map<String, String> emailToNameMap = new HashMap<>();
int emailCount = 0;
for (List<String> account : accounts) {
String name = account.getFirst();
for (int i = 1; i < account.size(); i++) {
String email = account.get(i);
if (!emailToNoMap.containsKey(email)) {
emailToNoMap.put(email, emailCount++);
emailToNameMap.put(email, name);
}
}
}
UnionFind uf = new UnionFind(emailCount);
for (List<String> account : accounts) {
String firstEmail = account.get(1);
Integer ai = emailToNoMap.get(firstEmail);
for (int j = 2; j < account.size(); j++) {
Integer bi = emailToNoMap.get(account.get(j));
uf.union(ai, bi);
}
}
Map<Integer, List<String>> noToEmailMap = new HashMap<>();
emailToNoMap.forEach((email, no) -> {
int id = uf.find(no);
List<String> emails = noToEmailMap.computeIfAbsent(id, v -> new ArrayList<>());
emails.add(email);
});
List<List<String>> result = new ArrayList<>();
for (List<String> emails : noToEmailMap.values()) {
List<String> account = new ArrayList<>(emails.size() + 1);
account.add(emailToNameMap.get(emails.getFirst()));
Collections.sort(emails);
account.addAll(emails);
result.add(account);
}
return result;
}
private static class UnionFind {
int[] parent;
public UnionFind(int size) {
this.parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public void union(int a, int b) {
int ap = find(a);
int bp = find(b);
if (ap == bp) {
return;
}
if (ap < bp) {
parent[bp] = ap;
} else {
parent[ap] = bp;
}
}
public int find(int a) {
int ap = parent[a];
List<Integer> path = new ArrayList<>();
path.add(a);
while (ap != parent[ap]) {
path.add(ap);
ap = parent[ap];
}
for (Integer i : path) {
parent[i] = ap;
}
return ap;
}
}