721. 账户合并

题目描述

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1：

输入：

[
    ["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：

输入：

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

解法一：哈希表 + 并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


type UnionFind struct {
    parent []int
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{parent: make([]int, n)}
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Find(i int) int {
    if uf.parent[i] != i {
        uf.parent[i] = uf.Find(uf.parent[i])
    }
    return uf.parent[i]
}

func (uf *UnionFind) Merge(i, j int) {
    uf.parent[uf.Find(i)] = uf.parent[uf.Find(j)]
}

func accountsMerge(accounts [][]string) [][]string {
    emailToIndex := make(map[string]int)
    indexToName := make(map[int]string)
    emailCount := 0
    for _, emails := range accounts {
        name := emails[0]
        for i := 1; i < len(emails); i++ {
            if _, has := emailToIndex[emails[i]]; !has {
                emailToIndex[emails[i]] = emailCount
                indexToName[emailCount] = name
                emailCount++
            }
        }
    }
    uf := NewUnionFind(emailCount)
    for _, emails := range accounts {
        indexA := emailToIndex[emails[1]]
        for i := 2; i < len(emails); i++ {
            indexB := emailToIndex[emails[i]]
            uf.Merge(indexA, indexB)
        }
    }
    var ans [][]string
    indexToEmails := make(map[int][]string)
    for email, index := range emailToIndex {
        rootIdx := uf.Find(index)
        indexToEmails[rootIdx] = append(indexToEmails[rootIdx], email)
    }
    for rootIdx, emails := range indexToEmails {
        infos := []string{indexToName[rootIdx]}
        sort.Slice(emails, func(i, j int) bool {
            return emails[i] < emails[j]
        })
        ans = append(ans, append(infos, emails...))
    }
    return ans
}