Home > Article > Web Front-end > js deduplication and optimization of numerical arrays
This time I will bring you js to deduplicate and optimize numerical arrays. What are the precautions for js to deduplicate and optimize numerical arrays? The following is a practical case, let’s take a look.
Preface
This article mainly introduces the relevant content about constructing a binary tree with js to deduplicate and optimize numerical arrays. It is shared for your reference. Learning, I won’t say much more below, let’s take a look at the detailed introduction.Common two-layer loop to implement array deduplication
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)
Build a binary tree to achieve deduplication (only applicable to Array of numerical type)
Construct the previously traversed elements into a binary tree. Each node in the tree satisfies: the value of the left child node< current The value of the node < The value of the right child nodeThis optimizes the process of judging whether the element has appeared beforeIf the element is larger than the current node, you only need to judge whether the element is in the node. It just has to appear in the right subtree of the nodeIf the element is smaller than the current node, you only need to determine whether the element has appeared in the left subtree of the nodelet 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)
Optimization idea one, record the maximum and minimum values
Record the maximum and minimum values of the inserted elements. If it is larger than the largest element or the smallest element is smaller, insert it directly
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)
Optimization idea two, build a red-black tree
Build a red-black tree and balance the height of the treeAbout the red-black tree Part, please see red-black tree insertionlet 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)
Other deduplication methods
Deduplication through Set object
[...new Set(arr)]Through
sort()
reduce() Method to remove duplicates
compare(2, '2') returns 0; and when reduce(), congruent comparison is performed
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)By
include<a href="http://www.php.cn/wiki/137.html" target="_blank">s() </a>
map() Method to remove duplicates
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))By
includes()
reduce() Method to remove duplication
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 }, [])Pair JSON object method through object key value
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)))I believe you have mastered the method after reading the case in this article, please come for more exciting information Pay attention to other related articles on php Chinese website! Recommended reading:
Angular uses ng-click to upload multiple parameters at the same time
What are the ways to implement letters in Angular Case conversion
The above is the detailed content of js deduplication and optimization of numerical arrays. For more information, please follow other related articles on the PHP Chinese website!