LeetCode 721. 账户合并
题目描述
题意分析
每个账户的第一项是名字，其余项是邮箱。共享邮箱的账户属于同一个人，这种关系可以传递；只同名而没有邮箱联系的账户不能合并。每个输出账户保留一个名字，邮箱去重后按字典序排列，各账户之间的输出顺序不限。
解法：并查集按邮箱建立账户关系
核心思路
[!blue]
把账户下标作为并查集节点。
owner[email]记录最早遇到这个邮箱的账户下标；再次遇到同一邮箱时，把当前账户与已记录账户合并即可。同一邮箱的所有账户都通过这个已记录账户连起来，无需两两比较账户或邮箱列表。
parent表示集合代表关系，find返回最终根并压缩沿途路径；union先找两个根，根不同才把较小集合接到较大集合上，并更新根的size。路径压缩不改变集合归属，按大小合并只影响选谁作为根，不影响要合并的两个集合。每次合并都有共享邮箱作为依据，不会凭名字误合并；所有共享邮箱关系又都会触发合并，因此直接相连或经其他账户间接相连的账户，最终恰好落在同一集合。
全部合并完成后，遍历
owner中的不同邮箱，通过find(owner[email])找到最终根并归组。记录邮箱时的账户下标可能后来被合并到其他根下，不能直接用它分组。题目保证同一个人的账户名字相同，所以输出时可取根账户的名字。
解题步骤
- 初始化并查集，每个账户自成一个集合，
owner为空。- 从每个账户的下标 1 开始遍历邮箱：首次出现则记录账户，已经出现则合并两个账户。
- 遍历
owner的键值对，重新查找登记账户的最终根，将邮箱加入该根对应的分组。哈希表每个邮箱只有一个键，因此这里不会重复处理相同邮箱。- Java 用
TreeSet维护组内顺序；Go 取出组内邮箱后调用sort.Strings排序，再在最前面加上名字。重复邮箱只会重复合并同一集合，不影响结果；没有共享关系的账户保留为独立集合。题目保证每个账户至少有一个邮箱，因此每个最终集合都会在邮箱分组阶段出现。
代码实现
class Solution {
// 一旦用并查集把共享邮箱对应的账户合并，问题就从字符串匹配变成了聚合每个连通分量里的邮箱集合。
public List<List<String>> accountsMerge(List<List<String>> accounts) {
int n = accounts.size();
DSU dsu = new DSU(n);
Map<String, Integer> owner = new HashMap<>();
for (int i = 0; i < n; i++) {
List<String> account = accounts.get(i);
for (int j = 1; j < account.size(); j++) {
String email = account.get(j);
Integer prev = owner.get(email);
if (prev == null) {
owner.put(email, i);
} else {
dsu.union(i, prev);
}
}
}
Map<Integer, TreeSet<String>> groups = new HashMap<>();
for (Map.Entry<String, Integer> entry : owner.entrySet()) {
// 全部合并后重新找最终根，首次登记账户未必仍是根
int root = dsu.find(entry.getValue());
groups.computeIfAbsent(root, k -> new TreeSet<>()).add(entry.getKey());
}
List<List<String>> answer = new ArrayList<>();
for (Map.Entry<Integer, TreeSet<String>> entry : groups.entrySet()) {
List<String> row = new ArrayList<>();
row.add(accounts.get(entry.getKey()).get(0));
row.addAll(entry.getValue());
answer.add(row);
}
return answer;
}
private static class DSU {
private final int[] parent;
private final int[] size;
DSU(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
int root = x;
while (parent[root] != root) {
root = parent[root];
}
while (parent[x] != x) {
int p = parent[x];
parent[x] = root;
x = p;
}
return root;
}
void union(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) {
return;
}
if (size[ra] < size[rb]) {
int t = ra;
ra = rb;
rb = t;
}
// 合并的是两个集合根，小集合挂入大集合
parent[rb] = ra;
size[ra] += size[rb];
}
}
}
import "sort"
type DSU struct {
// 一旦用并查集把共享邮箱对应的账户合并，问题就从字符串匹配变成了聚合每个连通分量里的邮箱集合。
parent []int
size []int
}
func newDSU(n int) *DSU {
parent := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
size[i] = 1
}
return &DSU{parent: parent, size: size}
}
func (d *DSU) find(x int) int {
root := x
for d.parent[root] != root {
root = d.parent[root]
}
for d.parent[x] != x {
p := d.parent[x]
d.parent[x] = root
x = p
}
return root
}
func (d *DSU) union(a, b int) {
ra := d.find(a)
rb := d.find(b)
if ra == rb {
return
}
if d.size[ra] < d.size[rb] {
ra, rb = rb, ra
}
// 合并的是两个集合根，小集合挂入大集合
d.parent[rb] = ra
d.size[ra] += d.size[rb]
}
type StringSet map[string]struct{}
func accountsMerge(accounts [][]string) [][]string {
n := len(accounts)
dsu := newDSU(n)
owner := make(map[string]int)
for i := 0; i < n; i++ {
for j := 1; j < len(accounts[i]); j++ {
email := accounts[i][j]
if prev, ok := owner[email]; ok {
dsu.union(i, prev)
} else {
owner[email] = i
}
}
}
groups := make(map[int]StringSet)
for email, idx := range owner {
// 全部合并后重新找最终根，首次登记账户未必仍是根
root := dsu.find(idx)
set, ok := groups[root]
if !ok {
set = make(StringSet)
groups[root] = set
}
set[email] = struct{}{}
}
answer := make([][]string, 0, len(groups))
for root, set := range groups {
emails := make([]string, 0, len(set))
for email := range set {
emails = append(emails, email)
}
sort.Strings(emails)
row := make([]string, 0, len(emails)+1)
row = append(row, accounts[root][0])
row = append(row, emails...)
answer = append(answer, row)
}
return answer
}
复杂度分析
- 时间复杂度：设 N 为账户数、E 为邮箱出现总次数、U 为不同邮箱数、L 为最长邮箱长度：可按期望 $O(N+EL+(E+U)\alpha(N)+UL\log(U+1))$ 估算，分别包含建表、合并、最终找根和组内排序。
- 空间复杂度：$O(N+U)$ 个账户与邮箱引用，不计已有字符串内容和输出。
关键点总结
[!green]
- 每个邮箱只需连接到一个已见拥有者，无需所有账户两两连边。
- 最终分组必须在全部 union 后重新 find。
- 邮箱唯一性由
owner的键保证，排序发生在各个合并后的组内，不能直接依赖哈希表遍历顺序。
易错点总结
[!yellow]
- 把名字也当邮箱，会错误合并所有同名账户。
- 按首次账户下标直接分组，会把已经合并的人拆开。
- 省略组内排序，不能满足邮箱的字典序要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 547. 省份数量 | 中等 | 同样求传递关联形成的连通分量，本题边由共享邮箱产生。 |
| 面试题 17.07. 婴儿名字 | 中等 | 同样把同义或共享关系合并为组，原题汇总名字频次，本题汇总邮箱并保留账号信息。 |
| 684. 冗余连接 | 中等 | 用并查集合并连通分量；本题按共享邮箱合并账户，该题找到使两端已经连通的多余边。 |
| 1319. 连通网络的操作次数 | 中等 | 用并查集合并连通分量；本题按共享邮箱合并账户，该题统计网络连通分量与可用冗余边。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！