JS numerical type array deduplication-JS Tutorial-php.cn

Home

Web Front-end

JS Tutorial

JS numerical type array deduplication

php中世界最好的语言

Jun 13, 2018 pm 04:04 PM

js Binary tree array

This time I will bring you the deduplication of JS numerical type arrays. What are the precautions for deduplication of JS numerical type arrays? The following is a practical case, let’s take a look.

Preface

This article mainly introduces the relevant content about constructing a binary tree with js to deduplicate and optimize numerical arrays. It is shared for your reference. Learning, I won’t say much more below, let’s take a look at the detailed introduction.

Common two-layer loop to implement array deduplication

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)

Copy after login

Build a binary tree to achieve deduplication (only applicable to numeric types array)

Construct the previously traversed elements into a binary tree. Each node in the tree satisfies: the value of the left child node< the value of the current node< The value of the right child node

This optimizes the process of determining whether the element has appeared before

If the element is larger than the current node, you only need to determine whether the element is in the right subtree of the node It only needs to appear before

If the element is smaller than the current node, you only need to determine whether the element has appeared in the left subtree of the node

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)

Copy after login

Optimization ideas 1. Record the maximum and minimum values

Record the maximum and minimum values of the inserted elements. If it is larger than the largest element or smaller than the smallest element, insert it directly

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)

Copy after login

Optimization idea two, build a red-black tree

Build a red-black tree, balance the height of the tree

For information about red-black trees, please see red-black Insertion of tree

100

101

102

103

104

105

106

107

108

109

110

111

112

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)

Copy after login

Other deduplication methods

##Deduplication through Set object

1	`[...new` `Set(arr)]`

Copy after login

Use

sort() reduce() method to remove duplicates

After sorting, compare adjacent elements to see if they are the same. If they are different, add them to the returned array

It is worth noting that when sorting, the default

compare(2, '2') returns 0; and when reduce(), perform congruent comparison

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 === 'number') {
    return -1
   } else {
    return 1
   }
  }
 }
}).reduce((pre, cur) => {
 if (pre !== cur) {
  newArr.push(cur)
  return cur
 }
 return pre
}, null)

Copy after login

pass

includes() map() Method to remove duplicates

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

Copy after login

includes() reduce() Method to remove duplicates

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = arr.reduce((pre, cur) => {
  !pre.includes(cur) && pre.push(cur)
  return pre
}, [])

Copy after login

Deduplication of JSON object methods through object key values

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 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)))

Copy after login

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress images for free

Clothoff.io

AI clothes remover

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

How to fix KB5055523 fails to install in Windows 11?

3 weeks ago By DDD

How to fix KB5055518 fails to install in Windows 10?

3 weeks ago By DDD

Roblox: Dead Rails - How To Tame Wolves

4 weeks ago By DDD

Strength Levels for Every Enemy & Monster in R.E.P.O.

3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Roblox: Grow A Garden - Complete Mutation Guide

2 weeks ago By DDD

Hot Tools

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial

1655

CakePHP Tutorial

1414

Laravel Tutorial

1307

PHP Tutorial

1254

C# Tutorial

1228

Related knowledge

Recommended: Excellent JS open source face detection and recognition project Apr 03, 2024 am 11:55 AM

Face detection and recognition technology is already a relatively mature and widely used technology. Currently, the most widely used Internet application language is JS. Implementing face detection and recognition on the Web front-end has advantages and disadvantages compared to back-end face recognition. Advantages include reducing network interaction and real-time recognition, which greatly shortens user waiting time and improves user experience; disadvantages include: being limited by model size, the accuracy is also limited. How to use js to implement face detection on the web? In order to implement face recognition on the Web, you need to be familiar with related programming languages and technologies, such as JavaScript, HTML, CSS, WebRTC, etc. At the same time, you also need to master relevant computer vision and artificial intelligence technologies. It is worth noting that due to the design of the Web side

How to remove duplicate elements from PHP array using foreach loop? Apr 27, 2024 am 11:33 AM

The method of using a foreach loop to remove duplicate elements from a PHP array is as follows: traverse the array, and if the element already exists and the current position is not the first occurrence, delete it. For example, if there are duplicate records in the database query results, you can use this method to remove them and obtain results without duplicate records.

The Art of PHP Array Deep Copy: Using Different Methods to Achieve a Perfect Copy May 01, 2024 pm 12:30 PM

Methods for deep copying arrays in PHP include: JSON encoding and decoding using json_decode and json_encode. Use array_map and clone to make deep copies of keys and values. Use serialize and unserialize for serialization and deserialization.

PHP array key value flipping: Comparative performance analysis of different methods May 03, 2024 pm 09:03 PM

The performance comparison of PHP array key value flipping methods shows that the array_flip() function performs better than the for loop in large arrays (more than 1 million elements) and takes less time. The for loop method of manually flipping key values takes a relatively long time.

PHP array multi-dimensional sorting practice: from simple to complex scenarios Apr 29, 2024 pm 09:12 PM

Multidimensional array sorting can be divided into single column sorting and nested sorting. Single column sorting can use the array_multisort() function to sort by columns; nested sorting requires a recursive function to traverse the array and sort it. Practical cases include sorting by product name and compound sorting by sales volume and price.

Application of PHP array grouping function in data sorting May 04, 2024 pm 01:03 PM

PHP's array_group_by function can group elements in an array based on keys or closure functions, returning an associative array where the key is the group name and the value is an array of elements belonging to the group.

Best Practices for Deep Copying PHP Arrays: Discover Efficient Methods Apr 30, 2024 pm 03:42 PM

The best practice for performing an array deep copy in PHP is to use json_decode(json_encode($arr)) to convert the array to a JSON string and then convert it back to an array. Use unserialize(serialize($arr)) to serialize the array to a string and then deserialize it to a new array. Use the RecursiveIteratorIterator to recursively traverse multidimensional arrays.

The role of PHP array grouping function in finding duplicate elements May 05, 2024 am 09:21 AM

PHP's array_group() function can be used to group an array by a specified key to find duplicate elements. This function works through the following steps: Use key_callback to specify the grouping key. Optionally use value_callback to determine grouping values. Count grouped elements and identify duplicates. Therefore, the array_group() function is very useful for finding and processing duplicate elements.

See all articles