ホームページ ウェブフロントエンド jsチュートリアル js を使用して数値配列を重複排除および最適化するバイナリ ツリーを構築する方法の詳細な説明

js を使用して数値配列を重複排除および最適化するバイナリ ツリーを構築する方法の詳細な説明

May 28, 2018 pm 05:33 PM
javascript 最適化 配列

この記事では、数値配列の重複排除と最適化を行うための 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)
ログイン後にコピー

重複排除を実装するためのバイナリ ツリーを構築します (数値型の配列にのみ適用可能)

通過した要素、バイナリ ツリーに構築され、ツリー内の各ノードは次の条件を満たします: 左のサブノードの値 < 現在のノードの値 < 右のサブノードの値

要素が以前に出現しました

If 要素が現在のノードより大きい場合は、その要素がノードの右側のサブツリーに出現したかどうかを判断するだけで済みます。要素が現在のノードより小さい場合は、判断するだけで済みます。要素がノードの左側のサブツリーに出現したかどうか

最適化のアイデア 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 オブジェクトを介してdeduplicate

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() メソッドにより、並べ替え後、隣接する要素が同じかどうかを比較します。それらは異なるため、返された配列に追加します

並べ替えの際、デフォルトの compare(2, '2') は 0 を返し、reduce() の場合は一致する比較を実行することに注意してください

[...new Set(arr)]
ログイン後にコピー

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.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)
ログイン後にコピー

通过 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))
ログイン後にコピー

通过 includes() + reduce()
includes() + map() メソッドを使用して重複を削除します

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() を使用して重複を削除します) + reduce() メソッド

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)))
ログイン後にコピー

オブジェクト + JSON オブジェクト メソッドのキーと値のペアを通じて重複を削除します

rrreee

上記皆さんのためにまとめたものです。今後皆さんのお役に立てれば幸いです。

関連記事:

Jquery1.8バージョンはajaxを使用してWeChat通話の問題分析と解決策を実装


軽量ajaxコンポーネントの作成01 - Webフォームプラットフォーム上のさまざまな実装方法との比較

分析とJquery Ajaxリクエストファイルのダウンロード操作が失敗する原因の解決策

🎜🎜🎜🎜🎜🎜🎜🎜

以上がjs を使用して数値配列を重複排除および最適化するバイナリ ツリーを構築する方法の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、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ヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

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++ プログラムの時間の複雑さを軽減するためのヒントには、適切なコンテナー (ベクター、リストなど) を選択して、データのストレージと管理を最適化することが含まれます。クイックソートなどの効率的なアルゴリズムを利用して計算時間を短縮します。複数の操作を排除して二重カウントを削減します。条件分岐を使用して、不必要な計算を回避します。二分探索などのより高速なアルゴリズムを使用して線形探索を最適化します。

PHP 配列の多次元ソートの実践: 単純なシナリオから複雑なシナリオまで PHP 配列の多次元ソートの実践: 単純なシナリオから複雑なシナリオまで Apr 29, 2024 pm 09:12 PM

多次元配列のソートは、単一列のソートとネストされたソートに分類できます。単一列のソートでは、array_multisort() 関数を使用して列ごとにソートできますが、ネストされたソートでは、配列を走査してソートするための再帰関数が必要です。具体的な例としては、製品名による並べ替えや、売上数量や価格による化合物の並べ替えなどがあります。

PHP 配列ディープ コピーの技術: さまざまな方法を使用して完璧なコピーを実現する PHP 配列ディープ コピーの技術: さまざまな方法を使用して完璧なコピーを実現する May 01, 2024 pm 12:30 PM

PHP で配列をディープ コピーする方法には、json_decode と json_encode を使用した JSON エンコードとデコードが含まれます。 array_map と clone を使用して、キーと値のディープ コピーを作成します。シリアル化と逆シリアル化には、serialize と unserialize を使用します。

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 で配列キー値を交換するための 3 つの一般的なアルゴリズムには、それぞれ長所と短所があります。 array_flip(): シンプルで効率的ですが、値は一意である必要があり、多次元配列を処理できません。手動トラバーサル: 多次元配列を処理し、例外を制御できますが、コードが長くなり、効率も低下します。 ksort()+array_keys(): あらゆるタイプの配列を処理し、ソート順序を制御できますが、効率は低くなります。実際のケースでは、array_flip() が最も効率的であることが示されていますが、多次元配列を扱う場合は、手動による走査の方が適切です。

See all articles