js构建二叉树进行数值数组的去重与优化详解
前言
本文主要介绍了关于js构建二叉树进行数值数组的去重与优化的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧。
常见两层循环实现数组去重
letarr=[11,12,13,9,8,7,0,1,2,2,5,7,11,11,7,6,4,5,2,2] letnewArr=[] for(leti=0;i构建二叉树实现去重(仅适用于数值类型的数组)
将先前遍历过的元素,构建成二叉树,树中每个结点都满足:左子结点的值<当前结点的值<右子结点的值
这样优化了判断元素是否之前出现过的过程
若元素比当前结点大,只需要判断元素是否在结点的右子树中出现过即可
若元素比当前结点小,只需要判断元素是否在结点的左子树中出现过即可
letarr=[0,1,2,2,5,7,11,7,6,4,5,2,2] classNode{ constructor(value){ this.value=value this.left=null this.right=null } } classBinaryTree{ constructor(){ this.root=null this.arr=[] } insert(value){ letnode=newNode(value) if(!this.root){ this.root=node this.arr.push(value) returnthis.arr } letcurrent=this.root while(true){ if(value>current.value){ if(current.right){ current=current.right }else{ current.right=node this.arr.push(value) break } } if(value优化思路一,记录最大最小值
记录已经插入元素的最大最小值,若比最大元素大,或最小元素小,则直接插入
letarr=[11,12,13,9,8,7,0,1,2,2,5,7,11,11,7,6,4,5,2,2] classNode{ constructor(value){ this.value=value this.left=null this.right=null } } classBinaryTree{ constructor(){ this.root=null this.arr=[] this.max=null this.min=null } insert(value){ letnode=newNode(value) if(!this.root){ this.root=node this.arr.push(value) this.max=value this.min=value returnthis.arr } if(value>this.max){ this.arr.push(value) this.max=value this.findMax().right=node returnthis.arr } if(valuecurrent.value){ if(current.right){ current=current.right }else{ current.right=node this.arr.push(value) break } } if(value 优化思路二,构建红黑树
构建红黑树,平衡树的高度
有关红黑树的部分,请见红黑树的插入
letarr=[11,12,13,9,8,7,0,1,2,2,5,7,11,11,7,6,4,5,2,2] console.log(Array.from(newSet(arr))) classNode{ constructor(value){ this.value=value this.left=null this.right=null this.parent=null this.color='red' } } classRedBlackTree{ constructor(){ this.root=null this.arr=[] } insert(value){ letnode=newNode(value) if(!this.root){ node.color='black' this.root=node this.arr.push(value) returnthis } letcur=this.root letinserted=false while(true){ if(value>cur.value){ if(cur.right){ cur=cur.right }else{ cur.right=node this.arr.push(value) node.parent=cur inserted=true break } } if(value其他去重方法
通过Set对象去重
[...newSet(arr)]通过sort()+reduce()方法去重
排序后比较相邻元素是否相同,若不同则添加至返回的数组中
值得注意的是,排序的时候,默认compare(2,'2')返回0;而reduce()时,进行全等比较
letarr=[0,1,2,'2',2,5,7,11,7,5,2,'2',2] letnewArr=[] arr.sort((a,b)=>{ letres=a-b if(res!==0){ returnres }else{ if(a===b){ return0 }else{ if(typeofa==='number'){ return-1 }else{ return1 } } } }).reduce((pre,cur)=>{ if(pre!==cur){ newArr.push(cur) returncur } returnpre },null)通过includes()+map()方法去重
letarr=[0,1,2,'2',2,5,7,11,7,5,2,'2',2] letnewArr=[] arr.map(a=>!newArr.includes(a)&&newArr.push(a))通过includes()+reduce()方法去重
letarr=[0,1,2,'2',2,5,7,11,7,5,2,'2',2] letnewArr=arr.reduce((pre,cur)=>{ !pre.includes(cur)&&pre.push(cur) returnpre },[])通过对象的键值对+JSON对象方法去重
letarr=[0,1,2,'2',2,5,7,11,7,5,2,'2',2] letobj={} arr.map(a=>{ if(!obj[JSON.stringify(a)]){ obj[JSON.stringify(a)]=1 } }) console.log(Object.keys(obj).map(a=>JSON.parse(a)))总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对毛票票的支持。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。