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

집

웹 프론트엔드

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, '2') 返回 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

위 내용은 모두를 위해 제가 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.

핫 AI 도구

Undresser.AI Undress

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

AI Clothes Remover

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

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

AI 옷 제거제

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

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

SublimeText3 중국어 버전

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

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

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

뜨거운 주제

Gmail 이메일의 로그인 입구는 어디에 있나요?

7695

자바 튜토리얼

1640

Cakephp 튜토리얼

1393

라라벨 튜토리얼

1287

PHP 튜토리얼

1229

Related knowledge

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

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

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

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

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

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

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

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

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

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

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

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

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

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