721. 账户合并
给定一个列表
accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
示例 1：
输入：accounts = [["John", "[email protected]", "[email protected]"], ["John", "[email protected]"], ["John", "[email protected]", "[email protected]"], ["Mary", "[email protected]"]] 输出：[["John", '[email protected]', '[email protected]', '[email protected]'], ["John", "[email protected]"], ["Mary", "[email protected]"]] 解释： 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "[email protected]"。 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。 可以以任何顺序返回这些列表，例如答案 [['Mary'，'[email protected]']，['John'，'[email protected]']， ['John'，'[email protected]'，'[email protected]'，'[email protected]']] 也是正确的。
示例 2：
输入：accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]] 输出：[["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
提示：
1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0]由英文字母组成
accounts[i][j] (for j > 0)是有效的邮箱地址
通过次数31,160提交次数65,895
法 1 并查集
思路
给每个 email 分配一个单独的id， 用于union find 操作。
关键是从 整理好的并查集 中取各元素对应值的操作。
题解
class Solution: def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]: uf = UnionFind(10001) email_to_name = {} email_to_id = {} id_ = 0 for i in range(len(accounts)): name = accounts[i][0] first_email = accounts[i][1] for j in range(1, len(accounts[i])): email = accounts[i][j] email_to_name[email] = name # 给每个email 分配一个id if email not in email_to_id: email_to_id[email] = id_ id_ += 1 # 把 该名字下面的所有email 都归为一类, 此时不用考虑姓名 uf.union(email_to_id[first_email], email_to_id[email]) res = collections.defaultdict(list) for email in email_to_name.keys(): idx = uf.find(email_to_id[email]) res[idx].append(email) # 添加名字 for idx, arr in res.items(): arr.sort() name = email_to_name[arr[0]] arr.insert(0, name) return list(res.values()) class UnionFind: def __init__(self, n): self.root = [i for i in range(n)] self.size = [0 for _ in range(n)] def find(self, x): if self.root[x] != x: self.root[x] = self.find(self.root[x]) return self.root[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: if self.size[root_x] < self.size[root_y]: self.root[root_x] = root_y self.size[root_y] += self.size[root_x] else: self.root[root_y] = root_x self.size[root_x] += self.size[root_y]