LeetCode（721. 賬戶合并）

給定一個串列 accounts，每個元素 accounts[i] 是一個字串串列，其中第一個元素 accounts[i][0] 是名稱 (name)，其余元素是 emails 表示該賬戶的郵箱地址，

現在，我們想合并這些賬戶，如果兩個賬戶都有一些共同的郵箱地址，則兩個賬戶必定屬于同一個人，請注意，即使兩個賬戶具有相同的名稱，它們也可能屬于不同的人，因為人們可能具有相同的名稱，一個人最初可以擁有任意數量的賬戶，但其所有賬戶都具有相同的名稱，

合并賬戶后，按以下格式回傳賬戶：每個賬戶的第一個元素是名稱，其余元素是按順序排列的郵箱地址，賬戶本身可以以任意順序回傳，

示例 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']] 也是正確的，

提示：

accounts的長度將在[1，1000]的范圍內，
accounts[i]的長度將在[1，10]的范圍內，
accounts[i][j]的長度將在[1，30]的范圍內，

來源：力扣（LeetCode）
鏈接：題目鏈接

題解：
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def union(self, index1: int, index2: int):
        self.parent[self.find(index2)] = self.find(index1)
    def find(self, index: int) -> int:
        if self.parent[index] != index:self.parent[index] = self.find(self.parent[index])
        return self.parent[index]
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

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/250767.html

標籤：python

上一篇：解決已利用pip安裝plotly庫但運行仍顯示ImportError: No module named ‘plotly‘方法（附帶模擬擲骰子代碼）

下一篇：C語言