웹 프론트엔드 JS 튜토리얼 js를 사용하여 이진 트리를 구성하는 숫자 배열의 중복 제거 및 최적화에 대한 자세한 설명

js를 사용하여 이진 트리를 구성하는 숫자 배열의 중복 제거 및 최적화에 대한 자세한 설명

May 28, 2018 pm 05:33 PM
javascript 최적화 정렬

이 기사에서는 숫자 배열을 중복 제거하고 최적화하기 위해 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 = &#39;red&#39;
 }
}

class RedBlackTree {
 constructor() {
  this.root = null
  this.arr = []
 }

 insert(value) {
  let node = new Node(value)
  if (!this.root) {
   node.color = &#39;black&#39;
   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 = &#39;black&#39;
   this.root = node
   return
  }
  if (node.parent.color === &#39;black&#39;) {
   return
  }
  let son = node
  let father = node.parent
  let grandFather = father.parent
  let directionFtoG = father === grandFather.left ? &#39;left&#39; : &#39;right&#39;
  let uncle = grandFather[directionFtoG === &#39;left&#39; ? &#39;right&#39; : &#39;left&#39;]
  let directionStoF = son === father.left ? &#39;left&#39; : &#39;right&#39;
  if (!uncle || uncle.color === &#39;black&#39;) {
   if (directionFtoG === directionStoF) {
    if (grandFather.parent) {
     grandFather.parent[grandFather.parent.left === grandFather ? &#39;left&#39; : &#39;right&#39;] = father
     father.parent = grandFather.parent
    } else {
     this.root = father
     father.parent = null
    }
    father.color = &#39;black&#39;
    grandFather.color = &#39;red&#39;

    father[father.left === son ? &#39;right&#39; : &#39;left&#39;] && (father[father.left === son ? &#39;right&#39; : &#39;left&#39;].parent = grandFather)
    grandFather[grandFather.left === father ? &#39;left&#39; : &#39;right&#39;] = father[father.left === son ? &#39;right&#39; : &#39;left&#39;]

    father[father.left === son ? &#39;right&#39; : &#39;left&#39;] = 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 = &#39;black&#39;
   uncle.color = &#39;black&#39;
   grandFather.color = &#39;red&#39;
   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, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 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 === &#39;number&#39;) {
    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, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))
로그인 후 복사
sort() + reduce() 方法去重

排序后比较相邻元素是否相同,若不同则添加至返回的数组中

值得注意的是,排序的时候,默认 compare(2, &#39;2&#39;) 返回 0;而 reduce() 时,进行全等比较

let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 2]
let newArr = arr.reduce((pre, cur) => {
  !pre.includes(cur) && pre.push(cur)
  return pre
}, [])
로그인 후 복사

通过 includes() + map() 方法去重

let arr = [0, 1, 2, &#39;2&#39;, 2, 5, 7, 11, 7, 5, 2, &#39;2&#39;, 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

PHP 배열 키 값 뒤집기: 다양한 방법의 성능 비교 분석 PHP 배열 키 값 뒤집기: 다양한 방법의 성능 비교 분석 May 03, 2024 pm 09:03 PM

PHP 배열 키 값 뒤집기 방법의 성능 비교는 array_flip() 함수가 대규모 배열(100만 개 이상의 요소)에서 for 루프보다 더 나은 성능을 발휘하고 시간이 덜 걸리는 것을 보여줍니다. 키 값을 수동으로 뒤집는 for 루프 방식은 상대적으로 시간이 오래 걸립니다.

C++ 프로그램 최적화: 시간 복잡도 감소 기술 C++ 프로그램 최적화: 시간 복잡도 감소 기술 Jun 01, 2024 am 11:19 AM

시간 복잡도는 입력 크기를 기준으로 알고리즘의 실행 시간을 측정합니다. C++ 프로그램의 시간 복잡성을 줄이는 팁에는 데이터 저장 및 관리를 최적화하기 위한 적절한 컨테이너(예: 벡터, 목록) 선택이 포함됩니다. Quick Sort와 같은 효율적인 알고리즘을 활용하여 계산 시간을 단축합니다. 여러 작업을 제거하여 이중 계산을 줄입니다. 불필요한 계산을 피하려면 조건부 분기를 사용하세요. 이진 검색과 같은 더 빠른 알고리즘을 사용하여 선형 검색을 최적화합니다.

PHP 배열 다차원 정렬 연습: 간단한 시나리오부터 복잡한 시나리오까지 PHP 배열 다차원 정렬 연습: 간단한 시나리오부터 복잡한 시나리오까지 Apr 29, 2024 pm 09:12 PM

다차원 배열 정렬은 단일 열 정렬과 중첩 정렬로 나눌 수 있습니다. 단일 열 정렬은 array_multisort() 함수를 사용하여 열별로 정렬할 수 있습니다. 중첩 정렬에는 배열을 순회하고 정렬하는 재귀 함수가 필요합니다. 실제 사례로는 제품명별 정렬, 판매량 및 가격별 복합 정렬 등이 있습니다.

PHP 어레이 딥 카피(Array Deep Copy) 기술: 다양한 방법을 사용하여 완벽한 카피 달성 PHP 어레이 딥 카피(Array Deep Copy) 기술: 다양한 방법을 사용하여 완벽한 카피 달성 May 01, 2024 pm 12:30 PM

PHP에서 배열을 깊게 복사하는 방법에는 json_decode 및 json_encode를 사용한 JSON 인코딩 및 디코딩이 포함됩니다. array_map 및 clone을 사용하여 키와 값의 전체 복사본을 만듭니다. 직렬화 및 역직렬화를 위해 직렬화 및 역직렬화를 사용합니다.

PHP 배열 심층 복사 모범 사례: 효율적인 방법 발견 PHP 배열 심층 복사 모범 사례: 효율적인 방법 발견 Apr 30, 2024 pm 03:42 PM

PHP에서 배열 전체 복사를 수행하는 가장 좋은 방법은 json_decode(json_encode($arr))를 사용하여 배열을 JSON 문자열로 변환한 다음 다시 배열로 변환하는 것입니다. unserialize(serialize($arr))를 사용하여 배열을 문자열로 직렬화한 다음 새 배열로 역직렬화합니다. RecursiveIteratorIterator를 사용하여 다차원 배열을 재귀적으로 순회합니다.

데이터 정렬에 PHP 배열 그룹화 기능 적용 데이터 정렬에 PHP 배열 그룹화 기능 적용 May 04, 2024 pm 01:03 PM

PHP의 array_group_by 함수는 키 또는 클로저 함수를 기반으로 배열의 요소를 그룹화하여 키가 그룹 이름이고 값이 그룹에 속한 요소의 배열인 연관 배열을 반환할 수 있습니다.

중복 요소를 찾는 데 있어 PHP 배열 그룹화 기능의 역할 중복 요소를 찾는 데 있어 PHP 배열 그룹화 기능의 역할 May 05, 2024 am 09:21 AM

PHP의 array_group() 함수를 사용하면 지정된 키로 배열을 그룹화하여 중복 요소를 찾을 수 있습니다. 이 함수는 다음 단계를 통해 작동합니다. key_callback을 사용하여 그룹화 키를 지정합니다. 선택적으로 value_callback을 사용하여 그룹화 값을 결정합니다. 그룹화된 요소 수를 계산하고 중복 항목을 식별합니다. 따라서 array_group() 함수는 중복된 요소를 찾고 처리하는 데 매우 유용합니다.

PHP 배열 키-값 교환: 일반적인 알고리즘의 장점과 단점 분석 PHP 배열 키-값 교환: 일반적인 알고리즘의 장점과 단점 분석 May 04, 2024 pm 10:39 PM

PHP에서 배열 키 값을 교환하는 세 가지 일반적인 알고리즘에는 고유한 장점과 단점이 있습니다. array_flip(): 간단하고 효율적이지만 값은 고유해야 하며 다차원 배열을 처리할 수 없습니다. 수동 순회: 다차원 배열을 처리하고 예외를 제어할 수 있지만 코드가 더 길고 효율성이 떨어집니다. ksort()+array_keys(): 모든 유형의 배열을 처리하고 정렬 순서를 제어할 수 있지만 효율성은 떨어집니다. 실제 사례에서는 array_flip()이 가장 효율적이라는 것을 보여주지만 다차원 배열을 처리할 때는 수동 순회가 더 적합합니다.

See all articles