721. 账户合并

721. 账户合并 #

链接 #

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) 是有效的邮箱地址

解答 #

这个问题可以通过使用并查集（Union-Find）数据结构来解决。并查集是一种用于处理一些不交集的合并及查询问题的数据结构。对于这个问题，我们可以将每个邮箱地址看作一个节点，如果两个邮箱地址属于同一个账户，则它们在并查集中是相连的。通过这种方式，我们可以找出所有属于同一个人的邮箱地址，并将它们合并到同一个账户下。

步骤：

  • 初始化并查集，每个邮箱地址自成一个集合。
  • 遍历所有账户，对于每个账户，将其中的邮箱地址进行合并。因为如果两个邮箱地址属于同一个账户，那么它们必定属于同一个人。
  • 在并查集中，合并所有属于同一个人的邮箱地址。
  • 遍历并查集中的所有集合，对于每个集合，找到其对应的账户名称，并将邮箱地址排序后添加到结果列表中。
class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    # 查找 x 的根节点，并初始化 x 的父节点和秩
    def find(self, x):
        # 如果 x 不在 parent 中，说明 x 还没有合并过，那么 x 就是自己的根节点
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 1 # 高度为 1，因为只有一个节点
            return x

        # 如果 x 的父节点不是自己，说明 x 不是根节点，那么就递归查找 x 的父节点的根节点
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    # 合并 x 和 y 所在的集合
    def union(self, x, y):
        # 找到它们的根节点
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return

        # 让高度较小的集合合并到高度较大的集合上
        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
               
class Solution:
    def accountsMerge(self, accounts):
        # 1. 完成每个 name 下的邮箱的根节点合并
        uf = UnionFind()
        email_to_name = {}
        for account in accounts:
            name = account[0]
            # 对于每个账户，将其中的邮箱地址进行合并
            for email in account[1:]:
                uf.find(email)
                email_to_name[email] = name
                # 跳过第一个邮箱，因为不需要自己和自己合并
                if account.index(email) > 1:
                    # 将剩下的邮箱合并
                    uf.union(email, account[1])

        # 在上面的代码中，我们完成了每个 name 下的邮箱的根节点合并
        # 例如，对于一个账户 ["John", "john01@mail.com", "john02@mail.com", "john03@mail.com"]，我们首先找到 “john01@mail.com” 的根节点，然后对于 “john02@mail.com” 和 “john03@mail.com”，我们也找到它们的根节点，并将它们与 “john01@mail.com” 的根节点进行合并。

        # 2. 找到每个邮箱的根节点，作为 key,然后将邮箱地址按照根节点分组
        root_to_emails = {}
        for email in email_to_name:
            root = uf.find(email)
            if root not in root_to_emails:
                root_to_emails[root] = []
            root_to_emails[root].append(email)

        # 3. 最后，遍历所有根节点，对于每个根节点，找到其对应的账户名称，并将邮箱地址排序后添加到结果列表中
        merged_accounts = []
        for root, emails in root_to_emails.items():
            emails.sort()
            merged_accounts.append([email_to_name[root]] + emails)

        return merged_accounts

并查集的 Rank 是什么？ #

在并查集数据结构中，rank 是一个辅助数据结构，通常与 parent 数组一起使用。rank 数组的目的是为了提高并查集的效率，特别是在进行 union 操作时。 rank 数组的作用是记录每个集合的“秩”（rank），这里的“秩”可以理解为树的高度或者深度。在进行 union 操作时，我们通常会按照秩来合并集合，这样可以避免树变得过高，从而减少查找根节点的时间复杂度。 具体来说，当我们要合并两个集合时，我们会比较这两个集合的秩：

  • 如果两个集合的秩不同，那么将秩较小的集合的根节点连接到秩较大的集合的根节点上，这样可以保持树的平衡。
  • 如果两个集合的秩相同，那么我们可以任选一个集合作为根，并将另一个集合连接到这个根上，然后增加这个根的秩。

通过这种方式，并查集可以在大部分情况下保持较好的平衡性，使得查找根节点的平均时间复杂度接近于常数时间 O(1)。

为什么让高度较小的集合合并到高度较大的集合上 #

将秩较小的集合的根节点连接到秩较大的集合的根节点上，这并不会立即导致新树的高度变为较大的秩。新树的高度实际上仍然是较大秩的值，因为我们只是将一个较小的子树连接到了一个较大的子树上，并没有增加较大子树的高度。

让我通过一个具体的例子来解释：

假设有两个集合：

  • 集合 A 的根节点是 A，秩为 1，它有一个子节点。
  • 集合 B 的根节点是 B，秩为 2，它有两个子节点。 现在，我们要合并这两个集合。按照秩来合并，我们会将集合 A 的根节点 A 连接到集合 B 的根节点 B 上。合并后的树如下：
      B (秩为 2)
     /   \
    A     其他节点
   /
  子节点

在这个例子中，合并后的树的高度仍然是 2，因为集合 B 的根节点 B 的秩是 2，我们只是将集合 A 作为集合 B 的一个子节点添加进去，并没有改变集合 B 的高度。如果我们在很多次合并操作中都遵循这个原则，那么整棵树的高度会保持在一个相对较低的水平，从而使得查找根节点的操作更加高效。

Edit Edit this page