今回は、JS 数値型配列の重複排除についてお届けします。JS 数値型配列の重複排除の注意点は次のとおりです。
はじめに
この記事では主に、数値配列の重複排除と最適化を行うための js によるバイナリ ツリーの構築に関する関連内容を紹介します。以下では多くを述べません。詳細な紹介をご覧ください。
配列の重複排除を実装するための一般的な 2 層ループ
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)
最適化アイデア 1、最大値と最小値を記録します 挿入された要素の最大値と最小値が最大の要素より大きい場合、または最小の要素より小さい場合は挿入します。直接それを
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)
最適化アイデア 2、赤黒ツリーを構築します 赤黒ツリーを構築し、ツリーの高さのバランスを取ります
赤黒ツリー部分については、の挿入を参照してください。赤黒ツリー
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()
メソッドを使用する重複を削除します
並べ替え後、隣接する要素が同じかどうかを比較し、異なる場合は返された配列に追加します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()
compare(2, '2')
はデフォルトで 0 を返します。 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 }, [])
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)))
以上がJS数値型配列の重複排除の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。