js를 사용하여 이진 트리 배열을 구성하기 위한 중복 제거 및 최적화 단계에 대한 자세한 설명
- php中世界最好的语言원래의
- 2018-05-03 11:09:061369검색
이번에는 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) 최적화 아이디어 하나, 최대값과 최소값을 기록하세요삽입된 요소의 최대값과 최소값을 기록하세요. 아니면 가장 작은 요소가 더 작으면 직접 삽입하세요
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)
通过 <a href="http://www.php.cn/wiki/137.html" target="_blank">include</a>s() + 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을 반환합니다. Reduce()에서는 합동 비교가 <a href="http%20://www.php.cn/%EC%9D%84%20%ED%86%B5%ED%95%B4%20</p><pre class="brush:php;toolbar:false">let%C2%A0arr%C2%A0=%C2%A0%5B0,%C2%A01,%C2%A02,%C2%A0'2',%C2%A02,%C2%A05,%C2%A07,%C2%A011,%C2%A07,%C2%A05,%C2%A02,%C2%A0'2',%C2%A02%5D%0D%0Alet%C2%A0newArr%C2%A0=%C2%A0arr.reduce((pre,%C2%A0cur)%C2%A0=>%C2%A0%7B%0D%0A%C2%A0%C2%A0!pre.includes(cur)%C2%A0&&%C2%A0pre.push(cur)%0D%0A%C2%A0%C2%A0return%C2%A0pre%0D%0A%7D,%C2%A0%5B%5D)</pre><p%20style=" text-align: left> 수행됩니다. wiki/137.html" target="_blank">include</a>
map() includes()를 통해 중복
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)))을 제거하는 방법 + reduce() 중복 제거 방법rrreee
객체의 키-값 쌍 + JSON 객체 방법을 통해 중복 제거rrreee이 글의 사례를 읽으신 후 방법을 마스터하셨을 거라 믿습니다. 더 흥미로운 콘텐츠를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!
추천 자료:
WeChat 애플릿은 페이지를 공유하고 홈페이지로 돌아갑니다
ElTableColumn은 검색 요약 기능을 추가합니다
위 내용은 js를 사용하여 이진 트리 배열을 구성하기 위한 중복 제거 및 최적화 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!