这次给大家带来js对数值数组进行去重与优化，js对数值数组进行去重与优化的注意事项有哪些，下面就是实战案例，一起来看一下。
前言
本文主要介绍了关于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 = 'red'
}
}
class redblacktree {
constructor() {
this.root = null
this.arr = []
}
insert(value) {
let node = new node(value)
if (!this.root) {
node.color = 'black'
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 = 'black'
this.root = node
return
}
if (node.parent.color === 'black') {
return
}
let son = node
let father = node.parent
let grandfather = father.parent
let directionftog = father === grandfather.left ? 'left' : 'right'
let uncle = grandfather[directionftog === 'left' ? 'right' : 'left']
let directionstof = son === father.left ? 'left' : 'right'
if (!uncle || uncle.color === 'black') {
if (directionftog === directionstof) {
if (grandfather.parent) {
grandfather.parent[grandfather.parent.left === grandfather ? 'left' : 'right'] = father
father.parent = grandfather.parent
} else {
this.root = father
father.parent = null
}
father.color = 'black'
grandfather.color = 'red'
father[father.left === son ? 'right' : 'left'] && (father[father.left === son ? 'right' : 'left'].parent = grandfather)
grandfather[grandfather.left === father ? 'left' : 'right'] = father[father.left === son ? 'right' : 'left']
father[father.left === son ? 'right' : 'left'] = 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 = 'black'
uncle.color = 'black'
grandfather.color = 'red'
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, '2', 2, 5, 7, 11, 7, 5, 2, '2', 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 === 'number') {
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, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newarr = []
arr.map(a => !newarr.includes(a) && newarr.push(a))
通过 includes() + reduce() 方法去重
let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newarr = arr.reduce((pre, cur) => {
!pre.includes(cur) && pre.push(cur)
return pre
}, [])
通过对象的键值对 + json 对象方法去重
let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 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)))
相信看了本文案例你已经掌握了方法，更多精彩请关注其它相关文章！
推荐阅读：
angular使用ng-click同时上传多个参数
angular有哪些方法可以实现字母大小写转换
以上就是js对数值数组进行去重与优化的详细内容。