Leetcode 721 账户合并

Leetcode 721: 账户合并 是一题典型的数据结构问题，考察图论、并查集以及深度优先搜索 (DFS) 的应用。题目要求对用户账户中重复的邮箱地址进行合并，合并后的结果按字典序排序。它强调 联合关系的处理能力。

题目描述

输入：一个列表 accounts，每个账号格式为：

accounts[i][0] 是账户名称；
accounts[i][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"]
]

解法 1：并查集 (Union-Find)

思路

核心问题：
- 如果两个账户有公共的邮箱地址，它们属于同一个人，所以需要将它们合并。
并查集思想：
- 用邮箱地址作为节点，将所有账户映射到邮箱地址的图中。
- 每个邮箱地址是一个点，若多个邮箱地址属于同一个用户，它们之间连边，归属于同一连通分量。
具体步骤：
- 遍历 accounts，用并查集将同一账户中所有邮箱进行合并；
- 遍历邮箱地址，按连通分量为不同账户分组；
- 返回结果时，对每个邮箱组按字典序排序。

代码模板

import java.util.*;class Solution {public List<List<String>> accountsMerge(List<List<String>> accounts) {Map<String, String> parent = new HashMap<>(); // 并查集的父节点Map<String, String> emailToName = new HashMap<>(); // 邮箱->用户名映射Map<String, TreeSet<String>> unions = new HashMap<>(); // 联通分量记录// 初始化每个邮箱的父节点为它自身，并建立邮箱到用户名的映射for (List<String> account : accounts) {String name = account.get(0);for (int i = 1; i < account.size(); i++) {String email = account.get(i);parent.putIfAbsent(email, email);emailToName.put(email, name);union(parent, account.get(1), email); // 合并当前邮箱与第一个邮箱}}// 查找每个邮箱的根节点，将其归类到对应连通块for (String email : parent.keySet()) {String root = find(parent, email); // 找当前邮箱的根unions.putIfAbsent(root, new TreeSet<>()); // 使用 TreeSet 进行排序unions.get(root).add(email);}// 组装结果List<List<String>> result = new ArrayList<>();for (String root : unions.keySet()) {List<String> emails = new ArrayList<>(unions.get(root));emails.add(0, emailToName.get(root)); // 加入用户名result.add(emails);}return result;}// 并查集的 "查找" 操作，带路径压缩private String find(Map<String, String> parent, String email) {if (!parent.get(email).equals(email)) {parent.put(email, find(parent, parent.get(email))); // 路径压缩}return parent.get(email);}// 并查集的 "合并" 操作private void union(Map<String, String> parent, String email1, String email2) {String root1 = find(parent, email1);String root2 = find(parent, email2);if (!root1.equals(root2)) {parent.put(root1, root2); // 合并为一个连通分量}}
}

复杂度分析

时间复杂度: O(n * α(n) + k log k)
- 遍历账户的并查集操作每次平均耗时 O(α(n))，其中 α 是阿克曼函数的反函数，近似为常数；
- 对每个连通分量进行排序，总体复杂度为 O(k log k)，其中 k 是邮箱总数。
空间复杂度: O(n + k)
- 使用并查集、映射表等存储邮箱及其对应关系。

解法 2：DFS（深度优先搜索）

思路

核心问题：
- 将每个邮箱视为图中的节点，并将不同账户中所有的邮箱构建成图。
- 如果某两个邮箱间有公共的账户，则它们之间有一条边。
- 求解同一用户的邮箱集合相当于求图中的连通分量。
具体步骤：
- 构建邮箱的图邻接表（每个邮箱存储它直接连接的邮箱）。
- 遍历图，仅对未访问的邮箱进行深度优先搜索，找到与之相连的所有邮箱节点；
- 整理得到最终结果。

代码模板

class Solution {public List<List<String>> accountsMerge(List<List<String>> accounts) {Map<String, List<String>> graph = new HashMap<>(); // 邻接表构建图Map<String, String> emailToName = new HashMap<>(); // 邮箱到用户名映射// 构建图for (List<String> account : accounts) {String name = account.get(0);for (int i = 1; i < account.size(); i++) {emailToName.put(account.get(i), name);graph.putIfAbsent(account.get(i), new ArrayList<>());if (i > 1) {// 创建双向连接graph.get(account.get(i - 1)).add(account.get(i));graph.get(account.get(i)).add(account.get(i - 1));}}}// 深度优先搜索获取连通块List<List<String>> result = new ArrayList<>();Set<String> visited = new HashSet<>();for (String email : graph.keySet()) {if (!visited.contains(email)) {List<String> emails = new ArrayList<>();dfs(graph, email, emails, visited); // 找到当前连通块Collections.sort(emails); // 按字典序排序emails.add(0, emailToName.get(email)); // 加入用户名result.add(emails);}}return result;}// 深度优先搜索private void dfs(Map<String, List<String>> graph, String email, List<String> emails, Set<String> visited) {visited.add(email); // 标记为访问emails.add(email); // 加入当前连通块for (String neighbor : graph.get(email)) {if (!visited.contains(neighbor)) {dfs(graph, neighbor, emails, visited); // 递归访问邻居}}}
}