Maison interface Web js tutoriel Explication détaillée de la déduplication et de l'optimisation des tableaux numériques à l'aide de js pour construire un arbre binaire

Explication détaillée de la déduplication et de l'optimisation des tableaux numériques à l'aide de js pour construire un arbre binaire

May 28, 2018 pm 05:33 PM
javascript 优化 数组

Cet article vous présente principalement les informations pertinentes sur la déduplication et l'optimisation des tableaux numériques à l'aide de js pour construire des arbres binaires. L'article les présente en détail à travers des exemples de codes. Il a une certaine valeur d'apprentissage de référence pour l'étude ou le travail de chacun. J’ai besoin d’amis, étudions ensemble.

Avant-propos

Cet article présente principalement le contenu pertinent sur la construction d'un arbre binaire avec js pour dédupliquer et optimiser des tableaux numériques. Il est partagé pour. votre référence. Learning, je n'en dirai pas plus ci-dessous, jetons un œil à l'introduction détaillée.

Boucle commune à deux couches pour implémenter la déduplication de tableau

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)
Copier après la connexion

Construire un arbre binaire pour réaliser la déduplication (applicable uniquement aux tableaux de type numérique)

Construire les éléments précédemment parcourus dans un arbre binaire. l'arbre Les nœuds satisfont tous : la valeur du sous-nœud gauche < la valeur du nœud actuel < la valeur du sous-nœud droit

Cela optimise le processus de jugement si l'élément est apparu before

if Si l'élément est plus grand que le nœud actuel, il vous suffit de déterminer si l'élément apparaît dans le sous-arbre droit du nœud

Si l'élément est plus petit que le nœud actuel, il vous suffit de déterminer si l'élément apparaît dans le sous-arbre gauche du nœud

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)
Copier après la connexion

Idée d'optimisation un, enregistrez le maximum et valeurs minimales

Enregistrez les valeurs maximales et minimales des éléments insérés S'il est plus grand que le plus grand élément ou plus petit que le plus petit élément, insérez directement.

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)
Copier après la connexion

Idée d'optimisation deux, construire un arbre rouge-noir

Construisez un arbre rouge-noir et équilibrez la hauteur de l'arbre

La partie sur les arbres rouge-noir, veuillez voir l'insertion de l'arbre rouge-noir

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)
Copier après la connexion

Autres méthodes de déduplication

Supprimer la duplication via l'objet Set

[...new Set(arr)]
Copier après la connexion

Supprimez les duplications via la méthode sort() + reduce()

Après le tri, comparez les éléments adjacents pour voir s'ils sont les idem. S'ils sont différents, ajoutez-les au tableau renvoyé

Il est à noter que lors du tri, la valeur par défaut compare(2, &#39;2&#39;) renvoie 0 tandis que réduire (), effectue une comparaison congruente

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)
Copier après la connexion

supprimer les doublons via la méthode includes() + map()

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))
Copier après la connexion

Déduplication via includes() + reduce() méthode

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
}, [])
Copier après la connexion

via une paire clé-valeur d'objet + déduplication de méthode d'objet JSON

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)))
Copier après la connexion

Ce qui précède est ce que j'ai compilé pour vous. J'espère que cela vous sera utile à l'avenir.

Articles connexes :

La version Jquery1.8 utilise ajax pour implémenter l'analyse des problèmes et les solutions pour les appels WeChat

Written Lightweight composant ajax 01 - Comparaison avec différentes méthodes d'implémentation sur la plateforme webform

Analyse des raisons et des solutions à l'échec de l'opération de téléchargement du fichier de requête Jquery Ajax

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Meilleurs paramètres graphiques
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Comment réparer l'audio si vous n'entendez personne
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Comment déverrouiller tout dans Myrise
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Inversion des valeurs clés du tableau PHP : analyse comparative des performances de différentes méthodes Inversion des valeurs clés du tableau PHP : analyse comparative des performances de différentes méthodes May 03, 2024 pm 09:03 PM

La comparaison des performances des méthodes de retournement des valeurs de clé de tableau PHP montre que la fonction array_flip() fonctionne mieux que la boucle for dans les grands tableaux (plus d'un million d'éléments) et prend moins de temps. La méthode de la boucle for consistant à retourner manuellement les valeurs clés prend un temps relativement long.

L'art de PHP Array Deep Copy : utiliser différentes méthodes pour obtenir une copie parfaite L'art de PHP Array Deep Copy : utiliser différentes méthodes pour obtenir une copie parfaite May 01, 2024 pm 12:30 PM

Les méthodes de copie approfondie de tableaux en PHP incluent : l'encodage et le décodage JSON à l'aide de json_decode et json_encode. Utilisez array_map et clone pour créer des copies complètes des clés et des valeurs. Utilisez Serialize et Unsérialize pour la sérialisation et la désérialisation.

Optimisation des programmes C++ : techniques de réduction de la complexité temporelle Optimisation des programmes C++ : techniques de réduction de la complexité temporelle Jun 01, 2024 am 11:19 AM

La complexité temporelle mesure le temps d'exécution d'un algorithme par rapport à la taille de l'entrée. Les conseils pour réduire la complexité temporelle des programmes C++ incluent : le choix des conteneurs appropriés (tels que vecteur, liste) pour optimiser le stockage et la gestion des données. Utilisez des algorithmes efficaces tels que le tri rapide pour réduire le temps de calcul. Éliminez les opérations multiples pour réduire le double comptage. Utilisez des branches conditionnelles pour éviter les calculs inutiles. Optimisez la recherche linéaire en utilisant des algorithmes plus rapides tels que la recherche binaire.

Pratique du tri multidimensionnel des tableaux PHP : des scénarios simples aux scénarios complexes Pratique du tri multidimensionnel des tableaux PHP : des scénarios simples aux scénarios complexes Apr 29, 2024 pm 09:12 PM

Le tri des tableaux multidimensionnels peut être divisé en tri sur une seule colonne et en tri imbriqué. Le tri sur une seule colonne peut utiliser la fonction array_multisort() pour trier par colonnes ; le tri imbriqué nécessite une fonction récursive pour parcourir le tableau et le trier. Les cas pratiques incluent le tri par nom de produit et le tri composé par volume de ventes et prix.

Meilleures pratiques pour la copie approfondie des tableaux PHP : découvrez des méthodes efficaces Meilleures pratiques pour la copie approfondie des tableaux PHP : découvrez des méthodes efficaces Apr 30, 2024 pm 03:42 PM

La meilleure pratique pour effectuer une copie complète d'un tableau en PHP consiste à utiliser json_decode(json_encode($arr)) pour convertir le tableau en chaîne JSON, puis à le reconvertir en tableau. Utilisez unserialize(serialize($arr)) pour sérialiser le tableau en chaîne, puis désérialisez-le en un nouveau tableau. Utilisez RecursiveIteratorIterator pour parcourir de manière récursive des tableaux multidimensionnels.

Application de la fonction de regroupement de tableaux PHP dans le tri des données Application de la fonction de regroupement de tableaux PHP dans le tri des données May 04, 2024 pm 01:03 PM

La fonction array_group_by de PHP peut regrouper des éléments dans un tableau en fonction de clés ou de fonctions de fermeture, renvoyant un tableau associatif où la clé est le nom du groupe et la valeur est un tableau d'éléments appartenant au groupe.

Le rôle de la fonction de regroupement de tableaux PHP dans la recherche d'éléments en double Le rôle de la fonction de regroupement de tableaux PHP dans la recherche d'éléments en double May 05, 2024 am 09:21 AM

La fonction array_group() de PHP peut être utilisée pour regrouper un tableau par une clé spécifiée afin de rechercher les éléments en double. Cette fonction fonctionne selon les étapes suivantes : Utilisez key_callback pour spécifier la clé de regroupement. Utilisez éventuellement value_callback pour déterminer les valeurs de regroupement. Comptez les éléments regroupés et identifiez les doublons. Par conséquent, la fonction array_group() est très utile pour rechercher et traiter des éléments en double.

Explorer la complexité des algorithmes de déduplication de tableaux PHP Explorer la complexité des algorithmes de déduplication de tableaux PHP Apr 28, 2024 pm 05:54 PM

Complexité de l'algorithme de déduplication de tableau PHP : array_unique() : O(n) array_flip()+array_keys() : O(n) boucle foreach : O(n^2)

See all articles