이 기사에서는 숫자 배열을 중복 제거하고 최적화하기 위해 js를 사용하여 이진 트리를 구성하는 방법에 대한 관련 정보를 주로 소개합니다. 이 기사는 샘플 코드를 통해 이를 매우 자세하게 소개합니다. 학습이나 작업이 필요한 모든 사람에게 도움이 되는 학습 가치가 있습니다. 아래에서 함께 공부해 보세요.
머리말
이 글은 숫자 배열의 중복을 제거하고 최적화하기 위해 js로 이진 트리를 구성하는 것과 관련된 내용을 주로 소개합니다. 아래에서는 많은 내용을 언급하지 않겠습니다. 자세한 소개를 보세요. Array 배열 중복 제거를 구현하기위한 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)로그인 후 복사
최적화 아이디어 1, 최대값과 최소값을 기록하세요
삽입된 요소의 최대값과 최소값을 기록하세요. .가장 큰 요소보다 크거나 가장 작은 요소가 작을 경우 직접 삽입하세요
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)로그인 후 복사
최적화 아이디어 2, 레드-블랙 트리 구축
레드-블랙 트리 구축 및 트리 높이의 균형을 맞추세요
레드-블랙 트리에 관한 부분은 레드-블랙 트리 삽입을 참조하세요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)로그인 후 복사
기타 중복 제거 방법
Set 객체를 통해 중복 제거
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)로그인 후 복사
sort() + reduce() 메소드를 통해 Re
정렬 후 인접한 요소를 비교하여 일치하는지 확인합니다. 동일하다면 반환된 배열에 추가하세요
정렬할 때 기본
compare(2, '2') 는 0을 반환하고, 감소()할 때,
includes() +
map() 메소드를 통해 합동 비교
[...new Set(arr)]
로그인 후 복사
를 수행하여 중복을 제거합니다.
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)로그인 후 복사
<를 통해 중복 제거 code>includes() + reduce() method
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))
로그인 후 복사
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.reduce((pre, cur) => {
!pre.includes(cur) && pre.push(cur)
return pre
}, [])로그인 후 복사
通过 includes() + map() 方法去重
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)))로그인 후 복사
通过 includes() + reduce()
객체의 키-값 쌍을 통해 중복 제거 + JSON 객체 method
rrreee
위 내용은 모두를 위해 제가 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.
관련 기사:
Jquery1.8 버전은 ajax를 사용하여 WeChat 통화에 대한 문제 분석 및 솔루션 구현
경량 ajax 구성 요소 작성 01 - 웹폼 플랫폼의 다양한 구현 방법과 비교
분석 및 Jquery Ajax 요청 파일 다운로드 작업 실패 원인에 대한 솔루션
위 내용은 js를 사용하여 이진 트리를 구성하는 숫자 배열의 중복 제거 및 최적화에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
