这个问题在这里已有答案：
解决以下问题的时间复杂度大约是多少？如果我们假设由于路径压缩，每次调用self.find（）大致摊销到~O（1）
问题陈述：
给定列表帐户，每个元素accounts [i]是字符串列表，其中第一个元素accounts [i] [0]是名称，其余元素是表示帐户电子邮件的电子邮件。
现在，我们想合并这些帐户。如果有两个帐户共有的电子邮件，则两个帐户肯定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但他们的所有帐户肯定具有相同的名称。
合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按排序顺序的电子邮件。帐户本身可以按任何顺序返回。
示例：输入：accounts = [[“John”，“johnsmith @ example.com”，“[email protected]”]，[“John”，“[email protected]”]，[“John”，“johnsmith @ example.com“，”john_newyork @ example.com“]，[”Mary“，”mary @ example.com“]]
输出：[[“John”，“john00 @ example.com”，“john_newyork @ example.com”，“johnsmith @ example.com”]，[“John”，“[email protected]”]，[“Mary” “，”mary @ example.com“]]
说明：第一个和第三个约翰是同一个人，因为他们有共同的电子邮件“[email protected]”。第二个John和Mary是不同的人，因为其他帐户都没有使用他们的电子邮件地址。我们可以按任何顺序返回这些列表，例如答案[['Mary'，'mary @ example.com']，['John'，'johnnybravo @ example.com']，['John'，'john00 @ example.com'，'john_newyork @ example.com'，'johnsmith @ example.com']]仍然会被接受。
class Solution:
def accountsMerge(self, accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
owners={}
parents={}
merged=collections.defaultdict(set)
results=[]
for acc in accounts:
for i in range(1,len(acc)):
owners[acc[i]] = acc[0]
parents[acc[i]] = acc[i]
for acc in accounts:
p = self.find(acc[1],parents) #Find parent of the first email in the list.
for i in range(2,len(acc)):
#Perform union find on the rest of the emails across all accounts (regardless of account name, as no common email can exist between different names.)
#Any common emails between any 2 lists will make those 2 lists belong to the same set.
currP = self.find(acc[i],parents)
if p!=currP:
parents[currP] = p
for acc in accounts:
p = self.find(acc[1],parents)
for i in range(1,len(acc)):
merged[p].add(acc[i])
for name,emails in merged.items():
res = [owners[name]] + sorted(emails)
results.append(res)
return results
def find(self,node,parents):
if node!=parents[node]:
parents[node] = self.find(parents[node],parents)
return parents[node]
检查代码，逐个部分：
for acc in accounts:
for i in range(1,len(acc)):
owners[acc[i]] = acc[0]
parents[acc[i]] = acc[i]
这是O（N），其中N是输入文本的大小，因为算法只访问输入的每个部分一次。请注意，每个文本元素可能具有任意大小，但这需要注意，因为N是输入文本的大小。
for acc in accounts:
p = self.find(acc[1],parents) #Find parent of the first email in the list.
for i in range(2,len(acc)):
currP = self.find(acc[i],parents)
if p!=currP:
parents[currP] = p
这也是O（N），因为：
self.find(acc[i], parents)被视为摊销O（1）。for acc in accounts:
p = self.find(acc[1],parents)
for i in range(1,len(acc)):
merged[p].add(acc[i])
循环本身取决于N - 输入文本的大小。 add()方法在一个集合上运行，在python中被认为是O（1）。总而言之，该块也需要O（N）。
for name,emails in merged.items():
res = [owners[name]] + sorted(emails)
results.append(res)
令人惊讶的是，这里存在瓶颈（至少在O符号方面）。 emails中的元素数量是O（N），因为很可能系统有一个拥有大部分电子邮件的大用户。这意味着sorted(emails)可以取O（N log N）。
排序后创建res的代码部分：
res = [owners[name]] + <the sort result>
这仅仅是排序数据大小的线性，它小于排序的O（N log N）。
尽管处于循环中，但排序的成本总计不超过O（N log N），因为O（N log N）的成本假设有一个大用户。不可能只有少数大用户。
例如，假设系统中有K个相等的用户。这使得每个用户的分类成本为O（N / K log（N / K））。对于整个系统，这总计为O（N log（N / K））。如果K是常数，则变为O（N log N）。如果K是N的函数，则O（N log（N / K））小于O（N log N）。这不是一个严格的证明，但足以得到基本的想法，为什么它是O（N log N）而不是更糟。
注意：复杂度计算有一个主要假设，即在Python中，通过长度为L的字符串键访问映射或集合是O（L）操作。这通常是正确的，有一个完美的哈希函数，Python没有。