/**
* @param {string[][]} accounts
* @return {string[][]}
*/
var accountsMerge = function (accounts) {
let emailToIndex = new Map(); //email对应的index
let emailToName = new Map(); //email对应的name
let emailsCount = 0; //email的index从0开始
for (let account of accounts) {
let name = account[0];
for (let i = 1; i < account.length; i++) {
let email = account[i];
if (!emailToIndex.has(email)) {
//相同的邮箱只能出现一次
emailToIndex.set(email, emailsCount++);
emailToName.set(email, name);
}
}
}
//并查集存储的是email的index 合并同一account中邮箱的index
let uf = new UnionSet(emailsCount);
for (let account of accounts) {
if (account.length <= 1) continue;
let firstEmail = account[1];
let firstIndex = emailToIndex.get(firstEmail);
for (let i = 2; i < account.length; i++) {
let otherEmail = account[i];
let otherIndex = emailToIndex.get(otherEmail);
uf.merge(firstIndex, otherIndex);
}
}
// 遍历emailToIndex中的所有email，通过查询并查集，将相同的email合并入数组
// 构建{rootIndex:emails}哈希表
let rootIndexToEmails = new Map();
for (let email of emailToIndex.keys()) {
let index = emailToIndex.get(email);
let rootIndex = uf.get(index);
let emails = rootIndexToEmails.has(rootIndex)
? rootIndexToEmails.get(rootIndex)
: [];
emails.push(email);
rootIndexToEmails.set(rootIndex, emails);
}
//按格式输出
let ans = [];
for (let emails of rootIndexToEmails.values()) {
let name = emailToName.get(emails[0]);
let sortedEmails = emails.sort();
let account = [name, ...sortedEmails];
ans.push(account);
}
return ans;
};
class UnionSet {
constructor(n) {
this.parent = new Array(n).fill(0).map((value, index) => index);
}
get(x) {
return (this.parent[x] =
this.parent[x] === x ? x : this.get(this.parent[x]));
}
merge(a, b) {
let rootA = this.get(a);
let rootB = this.get(b);
if (rootA === rootB) return;
this.parent[rootA] = rootB;
}
}手写思路：
