題目概述
給定一個串列 accounts，每個元素 accounts[i] 是一個字串串列，其中第一個元素 accounts[i][0] 是 名稱 (name)，其余元素是 emails，表示該賬戶的郵箱地址，
現在，我們想合并這些賬戶，如果兩個賬戶都有一些共同的郵箱地址，則兩個賬戶必定屬于同一個人，請注意，即使兩個賬戶具有相同的名稱，它們也可能屬于不同的人，因為人們可能具有相同的名稱，一個人最初可以擁有任意數量的賬戶，但其所有賬戶都具有相同的名稱，
合并賬戶后，按以下格式回傳賬戶：每個賬戶的第一個元素是名稱，其余元素是按字符 ASCII 順序排列的郵箱地址，賬戶本身可以以任意順序回傳，
示例 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]的范圍內，
解題思路
本題可以使用并查集解決，具體什么是并查集，可以看看這篇博客 https://blog.csdn.net/bjweimengshu/article/details/108332389
根據題目要求，兩個賬戶只要有一個郵箱相同，那么就認為是同一個人，因此我們以下標表示用戶，把所有屬于同一個人的用戶（下標）使用并查集連接起來，接下來嘛 ，，，我也不知道怎么描述，看代碼吧
class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
// 創建一個 HashMap，通過下列的回圈操作可以得知
// 最終每個郵箱都會對應它所屬的某一個用戶id
Map<String, Integer> emailToId = new HashMap<>();
int accountsLen = accounts.size();
UnionFind union = new UnionFind(accountsLen);
for(int i = 0; i < accountsLen; i++) {
int emailsLen = accounts.get(i).size();
for(int j = 1; j < emailsLen; j++) {
String curEmail = accounts.get(i).get(j);
if(emailToId.containsKey(curEmail)) {
union.merge(emailToId.get(curEmail), i);
} else {
emailToId.put(curEmail, i);
}
}
}
// 將用戶id與其擁有的所有email對應起來
Map<Integer, List<String>> idToEmail = new HashMap<>();
for(Map.Entry<String, Integer> entry : emailToId.entrySet()) {
// 首先要找到父id
int id = union.getFather(entry.getValue());
// 父id擁有的emails一定是連接集合中所有用戶所共有的
List<String> emails = idToEmail.getOrDefault(id, new LinkedList<>());
// 再把缺少的email添加到emails中
emails.add(entry.getKey());
idToEmail.put(id, emails);
}
// 將id與用戶名對應即可
List<List<String>> result = new LinkedList<>();
for (Map.Entry<Integer,List<String>> entry : idToEmail.entrySet()) {
List<String> list = entry.getValue();
Collections.sort(list);
list.add(0, accounts.get(entry.getKey()).get(0));
result.add(list);
}
return result;
}
class UnionFind {
int[] f;
public UnionFind(int n) {
f = new int[n];
for(int i = 0; i < n; i++) {
f[i] = i;
}
}
public int getFather(int index) {
return f[index] == index ? index : getFather(f[index]);
}
public void merge(int index1, int index2) {
f[getFather(index1)] = getFather(index2);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251499.html
標籤：其他
上一篇：2021寒假每日一題《貨幣系統》
下一篇：2021寒假每日一題《棋盤挑戰》