本文主要為大家介紹了關於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)
優化思路二,建構紅黑樹
建立紅黑樹,平衡樹的高度有關紅黑樹的部分,請見紅黑樹的插入
#[...new Set(arr)]
#透過Set 物件重
########################################################################### # #########
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)###透過###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.map(a => !newArr.includes(a) && newArr.push(a))###透過###includes() ###+ ###map() ###方法去重##### ##########
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 }, [])###透過###includes()### + ###reduce() ###方法去重############# ##
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)))###透過物件的鍵值對+ JSON 物件方法去重################rrreee###相關推薦:########## ##陣列PHP二維陣列的去重問題解析############JS陣列去重方法總結############JavaScript陣列去重的幾種方法分享##################
以上是js二元樹進行數值數組的去重與最佳化的詳細內容。更多資訊請關注PHP中文網其他相關文章!