LeetCode上合并问题，记录下解题思路
又是并查集，我现在看到这种类型的题目只会想到并查集了.....
可以拆分为以下2个问题：
- 怎么确认2个信息属于同一个人
- 确认完同一人之后如何合并信息
使用并查集确认同一人，需要判断两个用户的信息中间有一个相同，就可以确定为同一人，并且把相同人的父节点属性都设为一样
用map来保存每个相同账户的所有信息
之后再通过set来去重，不过要注意，这个根据题意需要排序输出所以还要加一道排序
// 定义一个节点
class user {
constructor (i) {
// 将自己的父亲设为自己
this.parent = this
// val属性记录下当前节点在accounts中的位置
this.val = i
}
}
// 定义查找函数，不断查找父节点，直到父节点等于本身
const find = function (x) {
while(x !== x.parent) {
x = x.parent
}
return x
}
var accountsMerge = function(accounts) {
// 保存账户数量长度
let len = accounts.length
// 用一个map保存同一用户的所有信息
let map = new Map()
// 建立对应长度的节点数组
let users = Array(len).fill(0).map((x,i) => new user(i))
// 返回结果
let res = []
// 遍历整个accounts数组，确立好每个用户之间的关系
for(let i = 0; i<len-1; i++) {
// 双重循环遍历，每一个都要和后面的对比多次
for(let j = i+1; j<len; j++) {
// accounts[i]和accounts[j]，名字不对比，后面的数据有一个相同就可以确认是同一账号
// 用到数组的some方法，some() 方法用于检测数组中的元素是否满足指定条件
var flag = accounts[i].some((item,k) => {
// 排除第一位名字的可能
// includes()是包含这个元素的话就返回true
return k!==0 && accounts[j].includes(item)
})
if(flag) {
// 如果标志位为true，那么就是包含相同的邮箱号
// 就要把j的父亲设为i
find(users[j]).parent = find(users[i])
}
}
}
// 然后遍历users数组，将父元素为同一节点的所有数据放在一起
for(let i =0;i<users.length;i++) {
// 查找到当前节点的父元素
let root = find(users[i])
if(map.has(root)) {
// 如果map中已经有这个节点的数据的话
map.get(root).push(accounts[i])
} else {
// 如果没有这个节点数据的话
map.set(root,[])
map.get(root).push(accounts[i])
}
}
// map中就是的每一项就是确认相同的
// 计算整合map就能得到结果，用set来去重
map.forEach(item => {
// 用flat来数据扁平化，sort进行排序，set来去重
let u = [...new Set(item.flat().sort())]
res.push(u)
})
return res
}
