js构建二叉树进行数值数组的去重与优化详解

2023-09-14 22:27:06 56
前言
本文主要介绍了关于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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
js构建二叉树进行数值数组的去重与优化详解

热门推荐

随机推荐
