账户合并Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给定一个列表 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) 是有效的邮箱地址
# 思路
连通图
# 解法
class Solution {
private int[] parent;
// 账户合并
public List<List<String>> accountsMerge(List<List<String>> accounts) {
// 初始化并查集
parent = new int[10000];
for (int i = 0; i < 10000; i++) {
parent[i] = i;
}
Map<String, String> emailToName = new HashMap<>();
Map<String, Integer> emailToId = new HashMap<>();
int id = 0;
for (List<String> account : accounts) {
String name = "";
String first = account.get(1);
for (String s : account) {
if (name.length() < 1) {
name = s;
continue;
}
emailToName.putIfAbsent(s, name);
emailToId.putIfAbsent(s, id++);
union(emailToId.get(first), emailToId.get(s));
}
}
Map<Integer, List<String>> ans = new HashMap<>();
for (String email : emailToName.keySet()) {
int par = find(emailToId.get(email));
ans.computeIfAbsent(par, v -> new ArrayList<>()).add(email);
}
for (List<String> component : ans.values()) {
Collections.sort(component);
component.add(0, emailToName.get(component.get(0)));
}
return new ArrayList<>(ans.values());
}
private int find(int node) {
return parent[node] == node ? node : (parent[node] = find(parent[node]));
}
private void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 == root2) {
return;
}
parent[root1] = root2;
}
}
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
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
# 总结
- 分析出几种情况,然后分别对各个情况实现