Jianbo Dai's

lc712.账户合并

 
  • Mar 13, 2021

题目链接

这个题又是经典的并查集题目。所以话不多说，但是一开始没有很多头绪，因为这个题里的name，email啥的比较复杂，需要引入一些哈希表才能更好更清晰地处理。如实现1所示，然后再在其中加入按秩排序（如实现2）。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。

python:

class UnionFind2:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def union(self, x, y):
        x_par, y_par = self.find(x), self.find(y)
				self.parent[x_par] = y_par

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]


class UnionFind1:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def union(self, x, y):
        x_par, y_par = self.find(x), self.find(y)
        if x_par != y_par:
            if self.rank[x_par] < self.rank[y_par]:
                x_par, y_par = y_par, x_par
            self.parent[y_par] = x_par 
            if self.rank[x_par] == self.rank[y_par]:
                self.rank[x_par] += 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        emailToIndex = dict()
        emailToName = dict()

        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in emailToIndex:
                    emailToIndex[email] = len(emailToIndex)
                    emailToName[email] = name
        
        uf = UnionFind(len(emailToIndex))
        for account in accounts:
            firstIndex = emailToIndex[account[1]]
            for email in account[2:]:
                uf.union(firstIndex, emailToIndex[email])
        
        indexToEmails = collections.defaultdict(list)
        for email, index in emailToIndex.items():
            index = uf.find(index)
            indexToEmails[index].append(email)
        
        ans = list()
        for emails in indexToEmails.values():
            ans.append([emailToName[emails[0]]] + sorted(emails))
        return ans

C++:

Search