js建構二元樹進行數值數組的去重與最佳化詳解-js教程-PHP中文網

首頁

web前端

js教程

js建構二元樹進行數值數組的去重與最佳化詳解

亚连

May 28, 2018 pm 05:33 PM

javascript 最佳化陣列

這篇文章主要為大家介紹了關於js建立二元樹進行數值數組的去重與優化的相關資料，文中透過範例程式碼介紹的非常詳細，對大家的學習或工作具有一定的參考學習價值，需要的朋友們下面一起學習學習吧。

前言

本文主要介紹了關於js建立二元樹進行數值陣列的去重與最佳化的相關內容，分享出來供大家參考學習，下面話不多說了，來一起看看詳細的介紹吧。

常見兩層循環實作陣列去重

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)

登入後複製

建構二元樹實現去重（僅適用於數值類型的陣列）

#將先前遍歷過的元素，建構成二元樹，樹中每個結點都滿足：左子結點的值< 當前結點的值< 右子結點的值

這樣優化了判斷元素是否之前出現過的過程

若元素比當前結點大，只需要判斷元素是否在結點的右子樹中出現過即可

若元素比目前結點小，只需要判斷元素是否在結點的左子樹中出現過即可

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)

登入後複製

最佳化想法一，記錄最大最小值

記錄已經插入元素的最大最小值，若比最大元素大，或最小元素小，則直接插入

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)

登入後複製

優化思路二，建構紅黑樹

建構紅黑樹，平衡樹的高度

有關紅黑樹的部分，請見紅黑樹的插入

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)

登入後複製

其他去重方法

透過Set物件去重

[...new Set(arr)]

登入後複製

#透過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.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() 方法去重

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
}, [])

登入後複製

透過物件的鍵值對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)))

登入後複製

#########上面是我整理給大家的，希望今後會對大家有幫助。 ######相關文章：#########jquery1.8版本使用ajax實作微信呼叫出現的問題分析及解決方法##############編寫輕量ajax元件01-與webform平台上的各種實作方式比較################Jquery Ajax請求檔下載操作失敗的原因分析及解決方案####### #####################

以上是js建構二元樹進行數值數組的去重與最佳化詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！

本網站聲明

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

免費脫衣圖片

Clothoff.io

AI脫衣器

Video Face Swap

使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！

熱工具

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

中文版，非常好用

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

gmail信箱登陸入口在哪裡

7753

Java教學

1643

CakePHP 教程

1398

Laravel 教程

1293

PHP教程

1234

Related knowledge

PHP數組深度複製的藝術：使用不同方法完美複製 May 01, 2024 pm 12:30 PM

PHP中深度複製數組的方法包括：使用json_decode和json_encode進行JSON編碼和解碼。使用array_map和clone進行深度複製鍵和值的副本。使用serialize和unserialize進行序列化和反序列化。

PHP 陣列鍵值翻轉：不同方法的效能比較分析 May 03, 2024 pm 09:03 PM

PHP數組鍵值翻轉方法效能比較顯示：array_flip()函數在大型數組（超過100萬個元素）下比for迴圈效能更優，耗時更短。手動翻轉鍵值的for迴圈方法耗時相對較長。

C++ 程式最佳化：時間複雜度降低技巧 Jun 01, 2024 am 11:19 AM

時間複雜度衡量演算法執行時間與輸入規模的關係。降低C++程式時間複雜度的技巧包括：選擇合適的容器（如vector、list）以最佳化資料儲存和管理。利用高效演算法（如快速排序）以減少計算時間。消除多重運算以減少重複計算。利用條件分支以避免不必要的計算。透過使用更快的演算法（如二分搜尋）來優化線性搜尋。

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迭代器對多維數組進行遞歸遍歷。