前言
并查集是合并汇合的形式，对于一些关联性的汇合，合并查问的形式能够使得题目分类解决，是一种题型的解决方案，这里最要害是构思好汇合之间的关联关系；
在这一 part 中，仅仅只是对局部题做了理解学习，远远没有达到能够手撕的水平，然而面试过程中遇到的并不算特地多，所以属于一个理解补充的 part，大家能够学习学习，还是挺有意思的；
下一 part 做分治法
注释
这是一篇水文，国庆回家也就保持每天做一丢丢题目，而后放弃一下手感，而并查集的确比拟好的锤炼一下脑子，脑子不够转不过去，所以能够尝试学习并做一下，他的根本模板不会很简单，根本如下：
class UnionFind { constructor(n){ // 缓存两个数组，父节点数组和以后节点的子节点数量数组 // 1. 初始化的父节点数组都是指向本人以后的下标的； -- 其中下标是惟一值 this.parents = new Array(n).fill(1).map((_,index) => index) // 2. 初始化的子节点数量数组都是只有一个；-- 其中下标是惟一值 this.sizes = new Array(n).fill(1) // } // 寻找 x 的根节点 find(x){ if(this.parents[x] === x) return x return this.find(this.parents[x]) } // 合并两个并查集 connect(x,y){ const px = this.find(x) const py = this.find(y) if(px === py) return // 如果他们是一个汇合，则间接返回 if(this.sizes[px]>this.sizes[py]){ // px 挂的节点更多，所以将 py 也挂过来 this.parents[py] =px this.sizes[px]++ }else{ this.parents[px] =py this.sizes[py]++ } }}当然，具体问题上，可能能够简化或者强化 connect 办法，来解决具体的问题，这就须要同学本人去学习探讨了；
最初将几道例题奉上，节日完结，持续搬砖吧；
参考视频：传送门
题目
547. 省份数量
剖析
- 每一个城市都有可能是一个省份，而只有是连贯的城市，就合并为一个省份，最初剩下的汇合就是省份
- 所以能够间接用 parents 数组缓存，其中 index 示意本人的惟一示意，value 示意指向汇合城市
- 当咱们遇到 isConnectedi === 1 的时候，将两个城市连接起来，最初失去的值就是连贯情况
- 最初的 parents[index] === index 的数量，就是汇合的数量
- 工夫复杂度 O(n), 空间复杂度 O(n)
var findCircleNum = function(isConnected) { const len = isConnected.length const parents = Array.from(isConnected).map((_,index) => index) // 指向本人 for(let i = 0;i<len;i++){ for(let j=0;j<len;j++){ if(isConnected[i][j] === 1){ _connect(i,j) // 将 i, j 合并 } } } return parents.filter((item,index) => item === index).length //筛选出根节点 function _connect(x,y) { parents[_find(x)] = _find(y) } function _find(x){ if(parents[x] ===x) return x return _find(parents[x]) }}// 规范类写法 class UnionFind { constructor(n){ // 缓存两个数组，父节点数组和以后节点的子节点数量数组 // 1. 初始化的父节点数组都是指向本人以后的下标的； -- 其中下标是惟一值 this.parents = new Array(n).fill(1).map((_,index) => index) // 2. 初始化的子节点数量数组都是只有一个；-- 其中下标是惟一值 this.sizes = new Array(n).fill(1) // } // 寻找 x 的根节点 find(x){ if(this.parents[x] === x) return x return this.find(this.parents[x]) } // 合并两个并查集 connect(x,y){ const px = this.find(x) const py = this.find(y) if(px === py) return // 如果他们是一个汇合，则间接返回 if(this.sizes[px]>this.sizes[py]){ // px 挂的节点更多，所以将 py 也挂过来 this.parents[py] =px this.sizes[px]++ }else{ this.parents[px] =py this.sizes[py]++ } }}var findCircleNum = function(isConnected) { const len = isConnected.length const unions = new UnionFind(isConnected.length) for(let i = 0;i<len;i++){ for(let j=0;j<len;j++){ if(isConnected[i][j] === 1){ unions.connect(i,j) // 将 i, j 合并 } } } console.log(unions) return new Set(unions.parents).size}721. 账户合并
剖析
- 首先题目已知邮箱属于惟一的一个name，而name的名字是能够雷同然而代表不同的人的，所以 name 只能算是一个标记而已,所以一开始做合并操作不须要计算 name，用 email_name_map 缓存起来，直到最初再用
- 因为邮箱是一个字符串，而这里显然须要将同一个用户的邮箱缓存到一起，所以这里用下标来标记不同的邮箱，并缓存到 email_index_map
- 开始应用并查集，将同一个用户下 email 连接起来
- 连贯完之后，当初在并查集 parents 外面都是一些 index 示意的货色，他们代表一种关联逻辑，
- 然而具体怎么重新排列，须要通过 email_index_map 来找到找到原始的 email,而后查找是否属于同一个汇合的，而后再缓存在在一起；
- 这个时候所有雷同汇合的值后缓存在了 email_index_map 的 value 中了，取出来，排序，而后从 email_name_map 取出 name，而后合并成一个数组，而后作为二维数组的一个 item push 到 merge 数组里
- 工夫复杂度 nlogn -- 每一次并查汇合并的时候，须要进行2次查找1次合并；空间复杂度 O(n)
var accountsMerge = function(accounts) { const email_index_map=new Map() const email_name_map=new Map() let emailIndex = 0 // 设置下标，作为惟一标识 -- 也代表了 emails 的数量 for (let i = 0; i < accounts.length; i++) { const account = accounts[i]; const name = account[0] for(let i = 1;i<account.length;i++){ const email = account[i] if(!email_index_map.has(email)){ email_index_map.set(email,emailIndex) email_name_map.set(email,name) emailIndex++ } } } const parents = Array.from({length:emailIndex}).map((_,index) => index) function _find(x){ if(parents[x]=== x) return x return _find(parents[x]) } function _connect(x,y) { const px = _find(x) const py = _find(y) parents[py] = px // 让 py 指向 py } // 开始应用并查集，将同一个用户下 email 连接起来 for (let i = 0; i < accounts.length; i++) { const firstEmail = accounts[i][1]; const firstIndex = email_index_map.get(firstEmail); for(let j = 2;j<accounts[i].length;j++){ const secondEmail = accounts[i][j]; const secondIndex = email_index_map.get(secondEmail); _connect(firstIndex,secondIndex) } } // 当初每一个 email 的关联关系都通过 index 连贯好了，当初须要用一个数据结构将他们取出来 // 这 key 值是根 emailIndex, values 就是这个汇合的 emails const index_email_map = new Map() for(let email of email_index_map.keys()) { const emailIndex = email_index_map.get(email) const root = _find(emailIndex) index_email_map.set(root,index_email_map.has(root)? [...index_email_map.get(root),email]:[email]) } const merge = [] for(let emailsArr of index_email_map.values()){ emailsArr.sort(); const name = email_name_map.get(emailsArr[0]) merge.push([name,...emailsArr]) } return merge}924. 尽量减少恶意软件的流传
剖析
- 创立并查集，并将能够连贯在一起的形成一个汇合
- 通过并查集，查找到每个并查集的 root 节点，并用 injectedMap 缓存根节点和对应的缺点节点数
- 初始化最大子节点数量 maxSize 和返回值 ret
- 再次遍历 initial 谬误节点，而后找到每个节点对应的根节点呈现的次数 count，如果超出 1， 那么干掉以后节点 node，仍然会有新的节点最初会感化 root 节点，也就是以后汇合还是会有感化源；所以没啥意思
- 如果都是只有一个感化源的汇合，那么就判断这个汇合的大小，汇合越大，则删除以后污染源节点成果更好；如果汇合一样大，就删除小的那一个；
- 工夫复杂度 O(n)，空间复杂度 O(n)
var minMalwareSpread = function (graph, initial) { const len = graph.length; const union = new UnionFind(len); for (let i = 0; i < len; i++) { for (let j = 0; j < len; j++) { if (graph[i][j] === 1) { union.connect(i, j); } } } // 感化源触发的根节点状态map，key 是感化源的根节点，value 是呈现次数 const injectedMap = new Map(); initial.forEach(node=> { const root = union.find(node) injectedMap.set(root,injectedMap.get(root)?injectedMap.get(root)+1:1)}) let maxSize = 0; // 符合要求的的汇合的数量 let ret = -1 initial.forEach(node => { // 找出感化源的根节点 const root = union.find(node) // 找出感化源的根节点呈现次数， -- 超出2个源头，就没有删除的成果了 const count = injectedMap.get(root) if(count === 1){ const size = union.sizes[root] // 看一下子节点有多少个 if(size>maxSize || (size === maxSize && node<ret)){ ret = node maxSize = size } } })// 如果 ret === -1, 则轻易删除一个节点，后果都是一样的，那么就删除其中最小的那个就好了 if(ret === -1) return Math.min(...initial) return ret};class UnionFind { constructor(len) { this.parents = Array.from({ length: len }).map((_, index) => index); this.sizes = new Array(len).fill(1); } find(x) { if (x === this.parents[x]) return x; return this.find(this.parents[x]); } connect(x, y) { const px = this.find(x); const py = this.find(y); if (px === py) return; if (this.sizes[px] > this.sizes[py]) { this.parents[py] = px; this.sizes[px] += this.sizes[py]; } else { this.parents[px] = py; this.sizes[py] += this.sizes[px]; } } }1319. 连通网络的操作次数
剖析
- 对于 n 台电脑，至多须要 n-1 条线能力把他们齐全连贯前来
- 对于 n 台机器，如果进行并查集连贯后，查看汇合的数量，咱们最初心愿只剩下一个 1 个汇合，多进去的汇合就是抽取网线进行操作的操作数量
- 并查集要害升高复杂度的操作 _find， 如果用的是迭代，那么就只须要遍历一遍，否则用递归就还要回来
- 最终的后果能够在 _connect 连贯过程中找出最终汇合的大小，也能够依据最初的 parents 的下标和值相等的值来获取
- 工夫复杂度 O(n)
var makeConnected = function (n, connections) { const len = connections.length // 网络连接数 if(len <n -1) return -1 // 如果len 小于 n-1 const parents = Array.from({length:n}).map((_,index) => index) const _find= (x) => { if( x !== parents[x]){ parents[x] = _find(parents[x]) } return parents[x] } let sizes = n const _connect = (x,y) => { const px= _find(x) const py= _find(y) if(px===py) return parents[px] = py sizes-- } for(let con of connections){ _connect(con[0],con[1]) // 连接起来 } return sizes-1}1202. 替换字符串中的元素
剖析 -- 超时了
- 一直的替换 pairs ，使得最终的字符串 str 是最小的字符串，所以就是要将 pairs 中同一汇合的找进去，按程序排好，而后再组合好
- 因为同一汇合之间能够联通，所以能够通过屡次之后，将汇合中最小的字符串放在其它字符之前
- 用一个 root_strArr 来缓存根节点下的字符串数组，而后每次合并的时候，依据 root_strArr 来拍平字符串的缓存，而后缓存两者的数组，最初失去根节点下缓存的汇合数组
- 最初在替换字符串的时候，每一次都找到这个汇合残余的最小的那个值，而后输入进来
- 超时了
- 而后认为做了一些轻微的优化，比方说字符串比拟比拟耗时，转成 Unicode 编码； 使自定义的有序数组合并等，然而都超时了
- 而后剖析工夫复杂度，如果在连贯过程中就进行排序操作，那么复杂度就是 O(n2) n 是 s.length, 而已知 s.length < 10^5, 所以 n2 超出了 10^8, 所以根本不能够通过了；
var smallestStringWithSwaps = function (s, pairs) { const parents = Array.from({ length: s.length }).map((_, index) => index); const root_strArr = Array.from({ length: s.length }).map((_, index) => [s[index].charCodeAt()]); const _find = (x) => { if (x !== parents[x]) { parents[x] = _find(parents[x]); } return parents[x]; }; const _connect = (x, y) => { const px = _find(x); const py = _find(y); if (px === py) return; if (root_strArr[px].length > root_strArr[py].length) { parents[py] = px; root_strArr[px] = _connectTwoArr(root_strArr[px],root_strArr[py]) } else { parents[px] = py; root_strArr[py]=_connectTwoArr(root_strArr[px],root_strArr[py]) } }; // 合并两个有序数组 const _connectTwoArr = (xArr,yArr) => { const xLen = xArr.length const yLen = yArr.length let x = y = 0 const ret = [] while(x<xLen && y<yLen){ if(xArr[x]>yArr[y]){ ret.push(yArr[y]) y++ }else{ ret.push(xArr[x]) x++ } } while(x<xLen) { ret.push(xArr[x]) x++ } while(y<yLen) { ret.push(yArr[y]) y++ } return ret } for (let p of pairs) { _connect(p[0], p[1]); } let ret = ""; for (let i = 0; i < s.length; i++) { const root = _find(i); // 看一下根节点 const arr = root_strArr[root]; // 找出这个根节点下的汇合，并找出 字典下的最小字符 const minStr = String.fromCharCode(arr.shift()); ret += minStr; } return ret;};剖析
- amazing，下面始终超时，始终想在连贯的时候进行排序操作，所以本人进行有序数组的排序，比拟转成 unicode 格局的，都超时了
- 反而在汇合合并的时候间接合并数组，而后在一次性将每个汇合进行排序，最初失去的后果能够 ac
- 遍历汇合数量，而后进行汇合排序，相当于是对所有字符的排序，工夫复杂度是 nlogn 其中 n 是 s.length;
var smallestStringWithSwaps = function (s, pairs) { const parents = Array.from({ length: s.length }).map((_, index) => index); const root_strArr = Array.from({ length: s.length }).map((_, index) => [s[index]]); const _find = (x) => { if (x !== parents[x]) { parents[x] = _find(parents[x]); } return parents[x]; }; const _connect = (x, y) => { const px = _find(x); const py = _find(y); if (px === py) return; if (root_strArr[px].length > root_strArr[py].length) { parents[py] = px; root_strArr[px].push(...root_strArr[py]) } else { parents[px] = py; root_strArr[py].push(...root_strArr[px]) } }; // 连贯 for (let p of pairs) { _connect(p[0], p[1]); } // 各个模块排序 root_strArr.map(arr => arr.sort()); let ret = ""; for (let i = 0; i < s.length; i++) { const root = _find(i); // 看一下根节点 const arr = root_strArr[root]; // 找出这个根节点下的汇合，并找出 字典下的最小字符 const minStr = arr.shift() ret += minStr; } return ret; };