Leetcode 721 账户合并

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

Solution

对于这题，我的第一反应不就是key-val转为val-key吗？所以果断的写下如下代码。

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        email_name_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_name_map:
                    email_name_map[email] = name
        # 最后根据name重新分组
        result = {}
        for email,name in email_name_map.items():
            if name not in result:
                result[name] = [name]
            result[name].append(email)
      
        res = []
        for k,v in result.items():
            res.append(v)
        return res
      

结果自然是全部报错：

× @test([["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]])

result:

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

expect:

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

---

可以发现，我们的结果将John的所有的邮箱合并在了一起。但是我们忽略了一种情况，即，同一个名字可能是两个不同的人啊。

所以说，我们应该转变思维，合并的依据不是有共同的名字，而是有共同的邮箱。

这个时候我们就需要知道每两个账户之间是否有重合账户，有的话即标记为1，否则标记为0。是否有重合账户我们可以用集合的交集来判断。这样的话我们可以用如下方法解决：

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        name_emails = []
        for account in accounts:
            name = account[0]
            name_emails = [[name,set(account[1:])]]
      
        n = len(name_emails)
      
        connections = [[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                if len(name_emails[i]&name_emails[j]) > 0:
                    connections[i][j] = 1
      
      

注意构造集合的时候，名字不能构造进去，不然同名同姓的两个人也会有交集的。

然后开始合并。

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        name_emails = []
        for account in accounts:
            name = account[0]
            name_emails = [[name,set(account[1:])]]
    
        n = len(name_emails)
    
        connections = [[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                if len(name_emails[i][1]&name_emails[j][1]) > 0:
                    connections[i][j] = 1
    
        res = []
        visited = []
        for i in range(n):
            if i in visited:
                continue
            res.append(name_emails[i])
            visited.append(i)
            for j in range(i,n):
                if connections[i][j] == 1:
                    visited.append(j)
                    res[-1][1] = res[-1][1] | name_emails[j][1]
    
        res = [[res[i][0]].extend(list(res[i][1])) for i in range(len(res))]
        return res

@test([["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]])

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

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

的确是解决了一部分问题，但是可能会漏掉一些应该合并的账户。例如，如果账户A和B有交集，B和C有交集，但A和C没有直接交集，代码可能不会将A、B、C全部合并。如果想要合并就需要多次迭代直到完全合并为止。

这种情况应该如何解决呢？带有间接的情况本质上就是各个账户之间形成了一个关系图，应该使用dfs和bfs了。直接从二维矩阵中进行dfs和bfs是比较麻烦的，这个时候我们就需要构造一个真正的图。

首先构建节点：

class Node:
    def __init__(self,id:int,account) -> None:
        self.id = id
        self.name = account[0]
        self.emails = set(account[1])
        self.linked_nodes = []
      
    def add_link(self,node):
        if node not in self.linked_nodes:
            self.linked_nodes.append(node)
            node.linked_nodes.append(self)

根据图的思路重新解决问题：

class Node:
    def __init__(self,id:int,account) -> None:
        self.id = id
        self.name = account[0]
        self.emails = set(account[1:])
        self.linked_nodes = []
      
    def add_link(self,node):
        if node not in self.linked_nodes:
            self.linked_nodes.append(node)
            node.linked_nodes.append(self)


class DFSNodes:
    def __init__(self,nodes:List[Node],visited:list) -> None:
        self.nodes = nodes
        self.visited = visited
        self.result = []
  
    def dfs(self,node:Node):
        if node is None: return 
        if node in self.visited: return 
        self.visited.append(node)
        self.result.extend(list(node.emails))
        for node_ in node.linked_nodes:
            self.dfs(node_)


class Solution:  
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)
        nodes = [Node(i,account) for i,account in enumerate(accounts)]
      
        # 建立节点之间的直接关联，形成图
        for i in range(n):
            for j in range(i+1,n):
                if len(nodes[i].emails & nodes[j].emails) > 0:
                    nodes[i].add_link(nodes[j])
                    nodes[j].add_link(nodes[i])
        # dfs 遍历
        merged_accounts = []
        visited = []
      
        for node in nodes:
            if node in visited: continue
            dfs_tool = DFSNodes(nodes,visited)
            dfs_tool.dfs(node)
            visited.extend(dfs_tool.visited)
            merged_accounts.append([node.name,set()])
            merged_accounts[-1][1] = merged_accounts[-1][1] | set(dfs_tool.result)
      
        result = []
        for item in merged_accounts:
            name = item[0]
            emails = list(item[1])
            result.append([name])
            result[-1].extend(emails)
      
        return result
      
          

@test([["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"]])  
result: [["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Kevin","Kevin0@m.co","Kevin5@m.co","Kevin3@m.co"],["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]] ,
expect: [["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"]]

看来是解决问题了。但是提交之后：

× @test([["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]])  
result: [["John","johnsmith@mail.com","john_newyork@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] ,
expect: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

看起来没问题，就是顺序不一样。

我们回头仔细审题，发现“合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回”

所以，我们需要再排个序。

class Node:
    def __init__(self,id:int,account) -> None:
        self.id = id
        self.name = account[0]
        self.emails = set(account[1:])
        self.linked_nodes = []
    
    def add_link(self,node):
        if node not in self.linked_nodes:
            self.linked_nodes.append(node)
            node.linked_nodes.append(self)


class DFSNodes:
    def __init__(self,nodes:List[Node],visited:list) -> None:
        self.nodes = nodes
        self.visited = visited
        self.result = []
  
    def dfs(self,node:Node):
        if node is None: return 
        if node in self.visited: return 
        self.visited.append(node)
        self.result.extend(list(node.emails))
        for node_ in node.linked_nodes:
            self.dfs(node_)


class Solution:  

    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)
        nodes = [Node(i,account) for i,account in enumerate(accounts)]
    
        # 建立节点之间的直接关联，形成图
        for i in range(n):
            for j in range(i+1,n):
                if len(nodes[i].emails & nodes[j].emails) > 0:
                    nodes[i].add_link(nodes[j])
                    nodes[j].add_link(nodes[i])
        # dfs 遍历
        merged_accounts = []
        visited = []
    
        for node in nodes:
            if node in visited: continue
            dfs_tool = DFSNodes(nodes,visited)
            dfs_tool.dfs(node)
            visited.extend(dfs_tool.visited)
            merged_accounts.append([node.name,set()])
            merged_accounts[-1][1] = merged_accounts[-1][1] | set(dfs_tool.result)
    
        result = []
        for item in merged_accounts:
            name = item[0]
            emails = list(item[1])
            emails.sort()
            result.append([name])
            result[-1].extend(emails)
    
        return result

现在是接受了。

但是，觉不觉得这个解法太复杂了。根据实测，时间复杂度和空间复杂度也是极高的，基本上是擦边过。其中最耗费时间和空间的就是dfs操作和构建关联的时候两次遍历。那么，有没有一种办法，可以根据数据只查询一次、不用像图一样需要经过复杂的遍历得到结果呢？

这个时候我们就要引入并查集。

并查集

并查集（Union-Find）是一种非常有用的数据结构，并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。它具有一些独特的特性，使其在特定场景下非常高效。让我介绍一下并查集的主要特性和典型应用场景：

并查集的特性：

• 快速合并（Union）操作：

可以快速将两个集合合并为一个。

• 快速查找（Find）操作：

可以快速确定一个元素属于哪个集合。

• 路径压缩：

在查找过程中，可以压缩查找路径，使得后续操作更快。

• 近乎常数时间复杂度：

经过优化后（如路径压缩和按秩合并），大多数操作的平均时间复杂度接近 O(1)。

5. 空间效率高：

只需要一个数组就可以表示复杂的集合关系。

6. 动态维护集合：

可以动态地添加新元素和合并集合。

7. 不支持分割操作：

一旦元素被合并到一个集合中，就不能再分割。

并查集的实现

class UnionFind:
    def __init__(self, n):
        # 初始化父节点数组和秩数组
        self.parent = list(range(n))
        self.rank = [0] * n
        # 记录集合的数量
        self.count = n

    def find(self, x):
        # 路径压缩：在查找的同时，将 x 到根节点路径上的所有节点直接连接到根节点
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
      
        # 如果 x 和 y 已经在同一个集合中，无需合并
        if root_x == root_y:
            return False

        # 按秩合并：将秩较小的树连接到秩较大的树上
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

        # 合并成功，集合数量减少
        self.count -= 1
        return True

    def connected(self, x, y):
        # 判断 x 和 y 是否在同一个集合中
        return self.find(x) == self.find(y)

    def get_count(self):
        # 获取当前的集合数量
        return self.count

估计还是晕晕乎乎的。无妨，我们直接用它来解决问题。

这个问题可以用并查集来解决，主要基于以下几个原因：

1. 分组问题：

本质上，这是一个分组或聚类问题。我们需要将属于同一个人的账户合并在一起。并查集非常适合处理这种需要动态合并集合的问题。

• 传递关系：

如果账户A和B有共同邮箱，B和C有共同邮箱，那么A、B、C都应该被合并。这种传递关系正是并查集所擅长处理的。

• 高效的合并操作：

在处理大量账户时，我们需要频繁地判断和合并账户。并查集提供了近乎常数时间的合并和查找操作，非常高效。

4. 动态性：

账户的合并是一个动态的过程，我们在遍历账户时逐步发现需要合并的关系。并查集可以很好地处理这种动态添加关系的场景。

5. 不需要拆分：

一旦确定两个账户属于同一个人，它们就应该永久合并。并查集正好不支持分割操作，符合这个特性。

那么，我们来重写代码，首先，每个集合里面的内容是姓名和邮箱，那么我们就需要为邮箱分配一个唯一ID：

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    
        email_id_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_id_map:
                    email_id_map[email] = len(email_id_map)

姓名信息也不能丢。

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    
        email_id_map = {}
        email_name_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_id_map:
                    email_id_map[email] = len(email_id_map)
                email_name_map[email] = name
      

好了，下面我们需要按照并查集的思路构建了。首先，先将所有的节点（邮箱）都认为是父节点，代表每个节点都是一个集合。

class UnionFind:
    def __init__(self,n) -> None:
        self.parent = [i for i in range(n)]


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    
        email_id_map = {}
        email_name_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_id_map:
                    email_id_map[email] = len(email_id_map)
                email_name_map[email] = name
         # 创建并查集
        n = len(email_id_map)
        uf_tool = UnionFind(n)

之后，再根据accounts中提供的信息，利用并查集的数据结构，动态的调整集合，调整到最后，剩余的父节点数量就是集合数量了。

• 遍历账户，根据账户提供的信息调整集合。

具体调整什么呢？就是将同一账号下的邮箱放到同一个集合下面。具体来说，就是将每个邮箱和第一个邮箱进行合并。

class UnionFind:
    def __init__(self,n) -> None:
        self.parent = [i for i in range(n)]
    
    def union(self,email1:str,email2:str):
        """
"""


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    
        email_id_map = {}
        email_name_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_id_map:
                    email_id_map[email] = len(email_id_map)
                email_name_map[email] = name
    
        # 创建并查集
        n = len(email_id_map)
        uf_tool = UnionFind(n)
    
        for account in accounts:
            for email in account[2:]:
                uf_tool.union(email_id_map[account[1]],email_id_map[email])

合并的时候具体怎么合并呢？对于传入的两个id，我们找找到它对应集合的根元素，第一次调用的时候，每个集合都只有一个根元素，就是它自身。对于有多个元素的集合，我们就要根据self.parent中的内容，依次向上查找，直到无法向上继续找（即，找到的向上的id还是它自身）。然后将其中一个根作为另一个根的父节点。这样，两棵树就变成一棵树了。

具体来说如下：

class UnionFind:
    def __init__(self,n) -> None:
        self.parent = [i for i in range(n)]
  
    def find(self,email_id):
        """
        查找x元素的根节点
        """
        while not self.parent[email_id] == email_id:  
            # 验证self.parent一直往上查，碰到自回环节点，说明到了初始设置的节点，这个节点就是根节点
            email_id = self.parent[email_id]
        return self.parent[email_id]

  
    def union(self,email_id1,email_id2):
        """
        将两个集合合并。
        """
        root_x, root_y = self.find(email_id1), self.find(email_id2)
        if root_x != root_y:
            self.parent[root_x] = root_y
    


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    
        email_id_map = {}
        email_name_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_id_map:
                    email_id_map[email] = len(email_id_map)
                email_name_map[email] = name
    
        # 创建并查集
        n = len(email_id_map)
        uf_tool = UnionFind(n)
    
        for account in accounts:
            for email in account[2:]:
                uf_tool.union(email_id_map[account[1]],email_id_map[email])

这样遍历一遍，集合自然而然就会被重组组织。这就是并查集的厉害之处。

下面将集合的结果进行重新组织：

class UnionFind:
    def __init__(self,n) -> None:
        self.parent = [i for i in range(n)]
  
    def find(self,email_id):
        """
        查找x元素的根节点
        """
        while not self.parent[email_id] == email_id:  
            # 验证self.parent一直往上查，碰到自回环节点，说明到了初始设置的节点，这个节点就是根节点
            email_id = self.parent[email_id]
        return self.parent[email_id]

  
    def union(self,email_id1,email_id2):
        """
        将两个集合合并。
        """
        root_x, root_y = self.find(email_id1), self.find(email_id2)
        if root_x != root_y:
            self.parent[root_x] = root_y
    


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    
        email_id_map = {}
        email_name_map = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_id_map:
                    email_id_map[email] = len(email_id_map)
                email_name_map[email] = name
    
        # 创建并查集
        n = len(email_id_map)
        uf_tool = UnionFind(n)
    
        for account in accounts:
            for email in account[2:]:
                uf_tool.union(email_id_map[account[1]],email_id_map[email])
    
        # 将各个集合的结果重新组织。根据根节点重新划分
        id_email_map = {}
        for email,id in email_id_map.items():
            root = uf_tool.find(id)
            if root not in id_email_map:
                id_email_map[root] = []
            id_email_map[root].append(email)
    
# 补充name
        result = []
        for emails in id_email_map.values():
            name = email_name_map[emails[0]]
            result.append([name]+sorted(emails))

        return result

到这里的性能就可以看了。当然，如果还想进一步优化，find函数还可以进行路径压缩。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
  
    def find(self,email_id):
        """
        查找x元素的根节点
        """
        if self.parent[email_id] != email_id:
            # 如果不是根节点，则递归找到根节点并将当前节点直接置于根节点之下
            self.parent[email_id] = self.find(self.parent[email_id])
        return self.parent[email_id]
    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        email_to_id = {}
        email_to_name = {}
      
        # 为每个邮箱分配一个唯一的ID
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in email_to_id:
                    email_to_id[email] = len(email_to_id)
                email_to_name[email] = name
      
        # 创建并查集
        uf = UnionFind(len(email_to_id))
      
        # 合并同一账户下的所有邮箱
        for account in accounts:
            for email in account[2:]:
                uf.union(email_to_id[account[1]], email_to_id[email])
      
        # 根据并查集结果重新组织邮箱
        id_to_emails = {}
        for email, id in email_to_id.items():
            root = uf.find(id)
            if root not in id_to_emails:
                id_to_emails[root] = []
            id_to_emails[root].append(email)
      
        # 构建最终结果
        result = []
        for emails in id_to_emails.values():
            name = email_to_name[emails[0]]
            result.append([name] + sorted(emails))
      
        return result

原文地址：https://blog.csdn.net/qq_34271349/article/details/142918185

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！