写点什么

JavaScript 刷 LeetCode 拿 offer- 并查集

作者:Geek_07a724
  • 2022-11-02
    浙江
  • 本文字数:6904 字

    阅读完需:约 23 分钟

前言

并查集是合并集合的方式,对于一些关联性的集合,合并查询的方式可以使得题目分类处理,是一种题型的解决方案,这里最关键是构思好集合之间的关联关系;


在这一 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. 省份数量

分析


  1. 每一个城市都有可能是一个省份,而只有是连接的城市,就合并为一个省份,最后剩下的集合就是省份

  2. 所以可以直接用 parents 数组缓存,其中 index 表示自己的唯一表示,value 表示指向集合城市

  3. 当我们遇到 isConnected[i][j] === 1 的时候,将两个城市连接起来,最后得到的值就是连接状况

  4. 最后的 parents[index] === index 的数量,就是集合的数量

  5. 时间复杂度 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. 账户合并

分析


  1. 首先题目已知邮箱属于唯一的一个 name,而 name 的名字是可以相同但是代表不同的人的,所以 name 只能算是一个标记而已,所以一开始做合并操作不需要计算 name,用 email_name_map 缓存起来,直到最后再用

  2. 由于邮箱是一个字符串,而这里显然需要将同一个用户的邮箱缓存到一起,所以这里用下标来标记不同的邮箱,并缓存到 email_index_map

  3. 开始使用并查集,将同一个用户下 email 连接起来

  4. 连接完之后,现在在并查集 parents 里面都是一些 index 表示的东西,他们代表一种关联逻辑,

  5. 但是具体怎么重新排列,需要通过 email_index_map 来找到找到原始的 email,然后查找是否属于同一个集合的,然后再缓存在在一起;

  6. 这个时候所有相同集合的值后缓存在了 email_index_map 的 value 中了,取出来,排序,然后从 email_name_map 取出 name,然后合并成一个数组,然后作为二维数组的一个 item push 到 merge 数组里

  7. 时间复杂度 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. 尽量减少恶意软件的传播

分析


  1. 创建并查集,并将可以连接在一起的构成一个集合

  2. 通过并查集,查找到每个并查集的 root 节点,并用 injectedMap 缓存根节点和对应的缺陷节点数

  3. 初始化最大子节点数量 maxSize 和返回值 ret

  4. 再次遍历 initial 错误节点,然后找到每个节点对应的根节点出现的次数 count,如果超出 1, 那么干掉当前节点 node,依然会有新的节点最后会感染 root 节点,也就是当前集合还是会有感染源;所以没啥意思

  5. 如果都是只有一个感染源的集合,那么就判断这个集合的大小,集合越大,则删除当前污染源节点效果更好;如果集合一样大,就删除小的那一个;

  6. 时间复杂度 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. 连通网络的操作次数

分析


  1. 对于 n 台电脑,至少需要 n-1 条线才能把他们完全连接前来

  2. 对于 n 台机器,如果进行并查集连接后,查看集合的数量,我们最后希望只剩下一个 1 个集合,多出来的集合就是抽取网线进行操作的操作数量

  3. 并查集关键降低复杂度的操作 _find, 如果用的是迭代,那么就只需要遍历一遍,否则用递归就还要回来

  4. 最终的结果可以在 _connect 连接过程中找出最终集合的大小,也可以根据最后的 parents 的下标和值相等的值来获取

  5. 时间复杂度 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. 交换字符串中的元素

分析 -- 超时了


  1. 不断的交换 pairs ,使得最终的字符串 str 是最小的字符串,所以就是要将 pairs 中同一集合的找出来,按顺序排好,然后再组合好

  2. 因为同一集合之间可以联通,所以可以经过多次之后,将集合中最小的字符串放在其它字符之前

  3. 用一个 root_strArr 来缓存根节点下的字符串数组,然后每次合并的时候,根据 root_strArr 来拍平字符串的缓存,然后缓存两者的数组,最后得到根节点下缓存的集合数组

  4. 最后在交换字符串的时候,每一次都找到这个集合剩余的最小的那个值,然后输出出去

  5. 超时了

  6. 然后以为做了一些细微的优化,比方说字符串比较比较耗时,转成 Unicode 编码; 使自定义的有序数组合并等,但是都超时了

  7. 然后分析时间复杂度,如果在连接过程中就进行排序操作,那么复杂度就是 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;};
复制代码


分析


  1. amazing,上面一直超时,一直想在连接的时候进行排序操作,所以自己进行有序数组的排序,比较转成 unicode 格式的,都超时了

  2. 反而在集合合并的时候直接合并数组,然后在一次性将每个集合进行排序,最后得到的结果可以 ac

  3. 遍历集合数量,然后进行集合排序,相当于是对所有字符的排序,时间复杂度是 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; };
复制代码


用户头像

Geek_07a724

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
JavaScript刷LeetCode拿offer-并查集_JavaScript_Geek_07a724_InfoQ写作社区