題目

給定一個列表 accounts，每個元素 accounts[i] 是一個字串列表，

其中第一個元素 accounts[i][0] 是 名稱 (name)，其餘元素是 emails 表示該賬戶的郵箱地址。

現在，我們想合併這些賬戶。如果兩個賬戶都有一些共同的郵箱地址，則兩個賬戶必定屬於同一個人。

請注意，即使兩個賬戶具有相同的名稱，它們也可能屬於不同的人，因為人們可能具有相同的名稱。

一個人最初可以擁有任意數量的賬戶，但其所有賬戶都具有相同的名稱。

合併賬戶後，按以下格式返回賬戶：每個賬戶的第一個元素是名稱，其餘元素是按順序排列的郵箱地址。

賬戶本身可以以任意順序返回。

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

提示：accounts的長度將在[1，1000]的範圍內。

accounts[i]的長度將在[1，10]的範圍內。

accounts[i][j]的長度將在[1，30]的範圍內。

解題思路分析

1、並查集；時間複雜度O(n^2log(n))，空間複雜度O(n^2)

func accountsMerge(accounts [][]string) [][]string {	n := len(accounts)	fa = Init(n)	res := make([][]string, 0)	m := make(map[string]int)	for i := 0; i < len(accounts); i++ {		for j := 1; j < len(accounts[i]); j++ {			email := accounts[i][j]			if id, ok := m[email]; ok { // 郵箱重複出現，合併賬戶				union(i, id)			} else {				m[email] = i			}		}	}	temp := make([][]string, n)	for k, v := range m {		target := find(v)		temp[target] = append(temp[target], k)	}	for i := 0; i < len(temp); i++ {		if len(temp[i]) > 0 {			arr := temp[i]			sort.Strings(arr)			arr = append([]string{accounts[i][0]}, arr...)			res = append(res, arr)		}	}	return res}var fa []int// 初始化func Init(n int) []int {	arr := make([]int, n)	for i := 0; i < n; i++ {		arr[i] = i	}	return arr}// 查詢func find(x int) int {	if fa[x] != x {		fa[x] = find(fa[x])	}	return fa[x]}// 合併func union(i, j int) {	fa[find(i)] = find(j)}

總結

Medium題目，並查集模板題目