721 账户合并（并查集）

系统管理员 2022-09-09 13:47 121阅读 0赞

**1. 问题描述：**

给定一个列表 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\] <= 30  
accounts\[i\]\[0\] 由英文字母组成  
accounts\[i\]\[j\] (for j > 0) 是有效的邮箱地址  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/accounts-merge

**2. 思路分析：**

分析题目可以知道邮箱才可以唯一标识当前的账户，所以我们可以使用哈希表将所有相同邮箱的账户编号放在一起，这样相同邮箱对应的编号属于同一个账户，然后我们需要合并这些相同邮箱对应的编号，合并编号之后我们才可以将这些编号对应的所有邮箱合并到某一个账户，合并集合中的元素可以使用**并查集**进行合并，也即将所有属于同一个集合中的编号合并到某一个节点中，使用列表\_res来记录编号对应的所有邮箱，最后遍历一下\_res，使用set集合去除掉重复的元素，并且加入当前编号对应的账户名称即可。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        # 在查找节点x的父节点的时候递归合并父节点
        def find(self, p: List[int], x: int):
            if x == p[x]: return p[x]
            p[x] = self.find(p, p[x])
            return p[x]
    
        # 因为需要合并集合所以使用并查集来解决
        def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
            n = len(accounts)
            # 并查集对应的父节点列表
            p = [i for i in range(n)]
            # 将相同邮箱的编号放在一起
            dic = collections.defaultdict(list)
            for i in range(len(accounts)):
                for j in range(1, len(accounts[i])):
                    # 哈希表记录的是相同邮箱的编号
                    dic[accounts[i][j]].append(i)
            for k, v in dic.items():
                root = self.find(p, v[0])
                for i in range(1, len(v)):
                    # 合并父节点, 将所有在同一个集合中编号合并到某一个节点
                    p[self.find(p, v[i])] = root
            # _res记录编号对应的所有邮箱
            _res = [list() for i in range(n)]
            for i in range(len(accounts)):
                for j in range(1, len(accounts[i])):
                    _res[self.find(p, i)].append(accounts[i][j])
            res = list()
            for i in range(len(_res)):
                # 因为邮箱可能是重复的所以需要使用set集合来去重
                _res[i] = list(set(_res[i]))
                # 对邮箱进行排序这样才可以满足按照字典序大小排序
                _res[i].sort()
                if len(_res[i]) > 0:
                    # 先加入邮箱对应的账户
                    t = [accounts[i][0]]
                    for x in _res[i]:
                        t.append(x)
                    res.append(t)
            return res