LeetCode 721. 账户合并

题目描述

给定一个列表 accounts，其中每个元素 accounts[i] 是一个字符串列表。第一个元素 accounts[i][0] 是名称，其余所有元素都是与该名称关联的电子邮件地址。

现在，我们需要合并这些账户。如果两个账户共享至少一个共同的电子邮件地址，则这两个账户必定属于同一个人。请注意，即使两个账户共享相同的名称，它们也可能属于不同的人，因为不同的人可能使用相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户必定具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 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"，所以它们属于同一个人，需要合并。

解题过程

这个问题本质上是一个连通性问题。我们需要找出哪些邮箱地址属于同一个人（即同一个连通分量），然后将它们合并。并查集（Union-Find） 是解决这类问题的理想数据结构。

步骤 1: 理解并查集的作用

并查集可以帮助我们高效地：

• 查找（Find）：确定某个元素属于哪个集合。
• 合并（Union）：将两个集合合并为一个。

在这里，每个邮箱地址是一个元素。如果两个邮箱出现在同一个账户中，或者通过其他邮箱间接关联，那么它们应该属于同一个集合（同一个人）。

步骤 2: 建立邮箱到账户名的映射

由于最终输出需要包含账户名，我们需要知道每个邮箱地址对应哪个名字。我们可以用一个字典（HashMap）来存储这个映射：email_to_name。

• 键：邮箱地址
• 值：账户名

注意：同一个邮箱地址不会出现在两个不同名称的账户中（题目保证）。在遍历账户建立此映射时，如果遇到重复邮箱（在同一人或不同人账户中），我们仍然用最后出现的名称覆盖，但根据问题描述，这通常不会发生，因为邮箱是唯一的标识。

步骤 3: 初始化并查集并连接邮箱

1. 初始化：创建一个并查集结构。我们需要将所有邮箱地址作为节点。但一开始我们不知道有多少个唯一的邮箱，所以我们可以在遍历过程中动态添加，或者先收集所有邮箱。

   • 更高效的做法是：遍历所有账户的所有邮箱，为每个邮箱分配一个唯一的并查集节点（通常用索引表示）。但我们可以直接用邮箱字符串本身作为键，在并查集中用字典来映射。

2. 连接同一账户内的邮箱：

   • 对于每个账户，将第一个邮箱与该账户中的其他所有邮箱进行 union 操作。
   • 为什么这样做？因为同一个账户中的所有邮箱已经属于同一个人。通过将第一个邮箱作为“代表”，我们可以确保它们都在同一个集合中。

步骤 4: 合并后分组

1. 使用一个字典 merged_emails：

   • 键：每个连通分量的根邮箱（通过 find 操作找到）
   • 值：该连通分量下的所有邮箱地址的集合（用 set 避免重复）

2. 遍历所有邮箱：

   • 对每个邮箱，找到它的根邮箱。
   • 将这个邮箱添加到根邮箱对应的集合中。

步骤 5: 格式化输出

对于每个连通分量（即 merged_emails 中的每个键）：

1. 获取根邮箱，通过 email_to_name 字典找到对应的账户名。
2. 将该账户名作为结果列表的第一个元素。
3. 将该连通分量下的所有邮箱地址排序（按字符 ASCII 顺序），并添加到结果列表中。
4. 将整个列表加入最终结果。

详细示例演示

以题目示例为例：

输入：

accounts = [
  ["John", "johnsmith@mail.com", "john00@mail.com"],      # 账户 A
  ["John", "johnnybravo@mail.com"],                       # 账户 B
  ["John", "johnsmith@mail.com", "john_newyork@mail.com"], # 账户 C
  ["Mary", "mary@mail.com"]                              # 账户 D
]

步骤执行：

1. 建立 email_to_name 映射：

   • "johnsmith@mail.com" -> "John"
   • "john00@mail.com" -> "John"
   • "johnnybravo@mail.com" -> "John"
   • "john_newyork@mail.com" -> "John"
   • "mary@mail.com" -> "Mary"

2. 初始化并查集，所有邮箱各自为政。

3. 连接邮箱：

   • 账户 A: 将 "johnsmith@mail.com" 和 "john00@mail.com" union。假设 "johnsmith@mail.com" 为根。
   • 账户 B: 只有一个邮箱，无需 union。
   • 账户 C: 将 "johnsmith@mail.com" 和 "john_newyork@mail.com" union。因为 "johnsmith@mail.com" 已经存在，所以 "john_newyork@mail.com" 会加入到它的集合。
   • 账户 D: 只有一个邮箱。

   现在，邮箱的分组情况是：

   • 组1: {"johnsmith@mail.com", "john00@mail.com", "john_newyork@mail.com"}（根可能是 "johnsmith@mail.com"）
   • 组2: {"johnnybravo@mail.com"}
   • 组3: {"mary@mail.com"}

4. 合并分组：

   • 根 "johnsmith@mail.com" 对应集合: {"johnsmith@mail.com", "john00@mail.com", "john_newyork@mail.com"}
   • 根 "johnnybravo@mail.com" 对应集合: {"johnnybravo@mail.com"}
   • 根 "mary@mail.com" 对应集合: {"mary@mail.com"}

5. 格式化输出：

   • 组1: 名称 "John"，邮箱排序后：['john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'] -> ["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']
   • 组2: ["John", 'johnnybravo@mail.com']
   • 组3: ["Mary", 'mary@mail.com']

最终输出：

[
  ["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
  ["John", 'johnnybravo@mail.com'],
  ["Mary", 'mary@mail.com']
]

关键点总结

• 使用并查集来高效合并关联的邮箱。
• 通过邮箱到名称的映射保留账户名信息。
• 同一账户内的邮箱通过 union 操作连接。
• 最后按根邮箱分组，排序后输出。

这个算法的时间复杂度接近线性（得益于并查集的路径压缩和按秩合并），能够高效处理大规模数据。