cari

Rumah >hujung hadapan web >tutorial js >js二叉树进行数值数组的去重与优化

js二叉树进行数值数组的去重与优化

小云云
小云云asal
2018-03-28 09:13:111296semak imbas

本文主要给大家介绍了关于js构建二叉树进行数值数组的去重与优化的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧。

常见两层循环实现数组去重


let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
let newArr = []
for (let i = 0; i < arr.length; i++) {
 let unique = true
 for (let j = 0; j < newArr.length; j++) {
  if (newArr[j] === arr[i]) {
   unique = false
   break
  }
 }
 if (unique) {
  newArr.push(arr[i])
 }
}
console.log(newArr)

构建二叉树实现去重（仅适用于数值类型的数组）

将先前遍历过的元素，构建成二叉树，树中每个结点都满足：左子结点的值 < 当前结点的值 < 右子结点的值

这样优化了判断元素是否之前出现过的过程

若元素比当前结点大，只需要判断元素是否在结点的右子树中出现过即可

若元素比当前结点小，只需要判断元素是否在结点的左子树中出现过即可


let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2]
class Node {
 constructor(value) {
  this.value = value
  this.left = null
  this.right = null
 }
}
class BinaryTree {
 constructor() {
  this.root = null
  this.arr = []
 }

 insert(value) {
  let node = new Node(value)
  if (!this.root) {
   this.root = node
   this.arr.push(value)
   return this.arr
  }
  let current = 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 < current.value) {
    if (current.left) {
     current = current.left
    } else {
     current.left = node
     this.arr.push(value)
     break
    }
   }
   if (value === current.value) {
    break
   }
  }
  return this.arr
 }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
 binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路一，记录最大最小值

记录已经插入元素的最大最小值，若比最大元素大，或最小元素小，则直接插入


let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
class Node {
 constructor(value) {
  this.value = value
  this.left = null
  this.right = null
 }
}
class BinaryTree {
 constructor() {
  this.root = null
  this.arr = []
  this.max = null
  this.min = null
 }

 insert(value) {
  let node = new Node(value)
  if (!this.root) {
   this.root = node
   this.arr.push(value)
   this.max = value
   this.min = value
   return this.arr
  }
  if (value > this.max) {
   this.arr.push(value)
   this.max = value
   this.findMax().right = node
   return this.arr
  }
  if (value < this.min) {
   this.arr.push(value)
   this.min = value
   this.findMin().left = node
   return this.arr
  }
  let current = 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 < current.value) {
    if (current.left) {
     current = current.left
    } else {
     current.left = node
     this.arr.push(value)
     break
    }
   }
   if (value === current.value) {
    break
   }
  }
  return this.arr
 }

 findMax() {
  let current = this.root
  while (current.right) {
   current = current.right
  }
  return current
 }

 findMin() {
  let current = this.root
  while (current.left) {
   current = current.left
  }
  return current
 }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
 binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路二，构建红黑树

构建红黑树，平衡树的高度

有关红黑树的部分，请见红黑树的插入


let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
console.log(Array.from(new Set(arr)))

class Node {
 constructor(value) {
  this.value = value
  this.left = null
  this.right = null
  this.parent = null
  this.color = &#39;red&#39;
 }
}

class RedBlackTree {
 constructor() {
  this.root = null
  this.arr = []
 }

 insert(value) {
  let node = new Node(value)
  if (!this.root) {
   node.color = &#39;black&#39;
   this.root = node
   this.arr.push(value)
   return this
  }
  let cur = this.root
  let inserted = 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 < cur.value) {
    if (cur.left) {
     cur = cur.left
    } else {
     cur.left = node
     this.arr.push(value)
     node.parent = cur
     inserted = true
     break
    }
   }

   if (value === cur.value) {
    break
   }
  }
  // 调整树的结构
  if(inserted){
   this.fixTree(node)
  }
  return this
 }

 fixTree(node) {
  if (!node.parent) {
   node.color = &#39;black&#39;
   this.root = node
   return
  }
  if (node.parent.color === &#39;black&#39;) {
   return
  }
  let son = node
  let father = node.parent
  let grandFather = father.parent
  let directionFtoG = father === grandFather.left ? &#39;left&#39; : &#39;right&#39;
  let uncle = grandFather[directionFtoG === &#39;left&#39; ? &#39;right&#39; : &#39;left&#39;]
  let directionStoF = son === father.left ? &#39;left&#39; : &#39;right&#39;
  if (!uncle || uncle.color === &#39;black&#39;) {
   if (directionFtoG === directionStoF) {
    if (grandFather.parent) {
     grandFather.parent[grandFather.parent.left === grandFather ? &#39;left&#39; : &#39;right&#39;] = father
     father.parent = grandFather.parent
    } else {
     this.root = father
     father.parent = null
    }
    father.color = &#39;black&#39;
    grandFather.color = &#39;red&#39;

    father[father.left === son ? &#39;right&#39; : &#39;left&#39;] && (father[father.left === son ? &#39;right&#39; : &#39;left&#39;].parent = grandFather)
    grandFather[grandFather.left === father ? &#39;left&#39; : &#39;right&#39;] = father[father.left === son ? &#39;right&#39; : &#39;left&#39;]

    father[father.left === son ? &#39;right&#39; : &#39;left&#39;] = grandFather
    grandFather.parent = father
    return
   } else {
    grandFather[directionFtoG] = son
    son.parent = grandFather

    son[directionFtoG] && (son[directionFtoG].parent = father)
    father[directionStoF] = son[directionFtoG]

    father.parent = son
    son[directionFtoG] = father
    this.fixTree(father)
   }
  } else {
   father.color = &#39;black&#39;
   uncle.color = &#39;black&#39;
   grandFather.color = &#39;red&#39;
   this.fixTree(grandFather)
  }
 }
}

let redBlackTree = new RedBlackTree()
for (let i = 0; i < arr.length; i++) {
 redBlackTree.insert(arr[i])
}
console.log(redBlackTree.arr)

其他去重方法

通过 Set 对象去重


[...new Set(arr)]

通过 sort() + reduce() 方法去重

排序后比较相邻元素是否相同，若不同则添加至返回的数组中

值得注意的是，排序的时候，默认 compare(2, '2') 返回 0；而 reduce() 时，进行全等比较


let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 2]
let newArr = []
arr.sort((a, b) => {
 let res = a - b
 if (res !== 0) {
  return res
 } else {
  if (a === b) {
   return 0
  } else {
   if (typeof a === &#39;number&#39;) {
    return -1
   } else {
    return 1
   }
  }
 }
}).reduce((pre, cur) => {
 if (pre !== cur) {
  newArr.push(cur)
  return cur
 }
 return pre
}, null)

通过 includes() + map() 方法去重


let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

通过 includes() + reduce() 方法去重


let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 2]
let newArr = arr.reduce((pre, cur) => {
  !pre.includes(cur) && pre.push(cur)
  return pre
}, [])

通过对象的键值对 + JSON 对象方法去重


let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 2]
let obj = {}
arr.map(a => {
  if(!obj[JSON.stringify(a)]){
    obj[JSON.stringify(a)] = 1
  }
})
console.log(Object.keys(obj).map(a => JSON.parse(a)))

相关推荐：

数组 PHP二维数组的去重问题解析

JS数组去重方法总结

JavaScript数组去重的几种方法分享

Atas ialah kandungan terperinci js二叉树进行数值数组的去重与优化. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan：
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel sebelumnya：node打造自己的命令行工具的方法Artikel seterusnya：红黑树的插入及Javascript实现方法详解

Artikel berkaitan

Lihat lagi