摘要:構(gòu)建二叉樹進(jìn)行數(shù)值數(shù)組的去重及優(yōu)化常見兩層循環(huán)實(shí)現(xiàn)數(shù)組去重構(gòu)建二叉樹實(shí)現(xiàn)去重僅適用于數(shù)值類型的數(shù)組將先前遍歷過的元素,構(gòu)建成二叉樹,樹中每個(gè)結(jié)點(diǎn)都滿足左子結(jié)點(diǎn)的值當(dāng)前結(jié)點(diǎn)的值右子結(jié)點(diǎn)的值這樣優(yōu)化了判斷元素是否之前出現(xiàn)過的過程若元素比當(dāng)前結(jié)點(diǎn)
構(gòu)建二叉樹進(jìn)行數(shù)值數(shù)組的去重及優(yōu)化 常見兩層循環(huán)實(shí)現(xiàn)數(shù)組去重
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)構(gòu)建二叉樹實(shí)現(xiàn)去重(僅適用于數(shù)值類型的數(shù)組)
將先前遍歷過的元素,構(gòu)建成二叉樹,樹中每個(gè)結(jié)點(diǎn)都滿足:左子結(jié)點(diǎn)的值 < 當(dāng)前結(jié)點(diǎn)的值 < 右子結(jié)點(diǎn)的值
這樣優(yōu)化了判斷元素是否之前出現(xiàn)過的過程
若元素比當(dāng)前結(jié)點(diǎn)大,只需要判斷元素是否在結(jié)點(diǎn)的右子樹中出現(xiàn)過即可
若元素比當(dāng)前結(jié)點(diǎn)小,只需要判斷元素是否在結(jié)點(diǎn)的左子樹中出現(xiàn)過即可
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)優(yōu)化思路一,記錄最大最小值
記錄已經(jīng)插入元素的最大最小值,若比最大元素大,或最小元素小,則直接插入
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)優(yōu)化思路二,構(gòu)建紅黑樹
構(gòu)建紅黑樹,平衡樹的高度
有關(guān)紅黑樹的部分,請見紅黑樹的插入
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 } } // 調(diào)整樹的結(jié)構(gòu) 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 對(duì)象去重
[...new Set(arr)]通過 sort() + reduce() 方法去重
排序后比較相鄰元素是否相同,若不同則添加至返回的數(shù)組中
值得注意的是,排序的時(shí)候,默認(rèn) compare(2, "2") 返回 0;而 reduce() 時(shí),進(jìn)行全等比較
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 }, [])通過對(duì)象的鍵值對(duì) + JSON 對(duì)象方法去重
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)))
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/107499.html
摘要:這是一個(gè)簡單的遞歸函數(shù),你可以使用它來生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu): 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸:遞歸是很多算法都使用的一種編程方法 - 如何將問題分成基線條件和遞歸條件 - 分而治之策略解決棘手問題 ...
摘要:這是一個(gè)簡單的遞歸函數(shù),你可以使用它來生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu): 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸:遞歸是很多算法都使用的一種編程方法 - 如何將問題分成基線條件和遞歸條件 - 分而治之策略解決棘手問題 ...
摘要:二叉樹二叉樹是一種樹形結(jié)構(gòu),它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn),一棵二叉樹通常由根節(jié)點(diǎn),分支節(jié)點(diǎn),葉子節(jié)點(diǎn)組成。 二叉樹 二叉樹(Binary Tree)是一種樹形結(jié)構(gòu),它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn),一棵二叉樹通常由根節(jié)點(diǎn),分支節(jié)點(diǎn),葉子節(jié)點(diǎn)組成。而每個(gè)分支節(jié)點(diǎn)也常常被稱作為一棵子樹。 showImg(https://segmentfault.com/img/bVbmEd...
摘要:前端面試總結(jié)先說背景,本人年月畢業(yè),去年十月校招到今年月一直在做前端開發(fā)工作,年前打算換工作,就重新梳理下面試考點(diǎn)總結(jié)包含基礎(chǔ),基礎(chǔ),常見算法和數(shù)據(jù)結(jié)構(gòu),框架,計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)知識(shí),可能有的點(diǎn)很細(xì),有的點(diǎn)很大,參考個(gè)人情況進(jìn)行總結(jié),方便對(duì)知識(shí) 前端面試總結(jié) 先說背景,本人2018年7月畢業(yè),去年十月校招到今年10月一直在做前端開發(fā)工作,年前打算換工作,就重新梳理下面試考點(diǎn)總結(jié)包含: ...
摘要:前端面試總結(jié)先說背景,本人年月畢業(yè),去年十月校招到今年月一直在做前端開發(fā)工作,年前打算換工作,就重新梳理下面試考點(diǎn)總結(jié)包含基礎(chǔ),基礎(chǔ),常見算法和數(shù)據(jù)結(jié)構(gòu),框架,計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)知識(shí),可能有的點(diǎn)很細(xì),有的點(diǎn)很大,參考個(gè)人情況進(jìn)行總結(jié),方便對(duì)知識(shí) 前端面試總結(jié) 先說背景,本人2018年7月畢業(yè),去年十月校招到今年10月一直在做前端開發(fā)工作,年前打算換工作,就重新梳理下面試考點(diǎn)總結(jié)包含: ...
閱讀 982·2023-04-26 01:47
閱讀 1672·2021-11-18 13:19
閱讀 2042·2019-08-30 15:44
閱讀 645·2019-08-30 15:44
閱讀 2291·2019-08-30 15:44
閱讀 1232·2019-08-30 14:06
閱讀 1420·2019-08-30 12:59
閱讀 1900·2019-08-29 12:49