What are the efficient algorithms in JavaScript?

This article mainly introduces five commonly used and efficient algorithms for deleting duplicate elements of arrays in JavaScript. It summarizes and analyzes several common operating techniques for deleting duplicate elements of arrays in JavaScript in the form of examples. Friends in need can refer to the following

The examples in this article describe five commonly used and efficient algorithms for deleting duplicate elements from arrays in JavaScript. Share it with everyone for your reference, the details are as follows:

Here are 5 methods on how to implement array deduplication in js, and a demo and source code are attached.

1. Array traversal method

The simplest method to remove duplicates,

Implementation ideas : Create a new array, traverse the incoming array, and add the value if it is not in the new array; Note: The method "indexOf" to determine whether the value is in the array is an ECMAScript5 method, which is not supported by IE8 and below. You need to write more for low compatibility version browser code, the source code is as follows:

// 最简单数组去重法
function unique1(array){
 var n = []; //一个新的临时数组
 //遍历当前数组
 for(var i = 0; i < array.length; i++){
  //如果当前数组的第i已经保存进了临时数组，那么跳过，
  //否则把当前项push到临时数组里面
  if (n.indexOf(array[i]) == -1) n.push(array[i]);
 }
 return n;
}
// 判断浏览器是否支持indexOf ，indexOf 为ecmaScript5新方法 IE8以下（包括IE8， IE8只支持部分ecma5）不支持
if (!Array.prototype.indexOf){
 // 新增indexOf方法
 Array.prototype.indexOf = function(item){
  var result = -1, a_item = null;
  if (this.length == 0){
   return result;
  }
  for(var i = 0, len = this.length; i < len; i++){
   a_item = this[i];
   if (a_item === item){
    result = i;
    break;
   } 
  }
  return result;
 }
}

2. Object key-value pair method

This method executes faster than any other method Fast, but it takes up more memory;

Implementation idea: Create a new js object and a new array. When traversing the incoming array, determine whether the value is the key of the js object. If not, give The key is added to the object and placed into a new array. Note: When determining whether it is a js object key, "toString()" will be automatically executed on the incoming key. Different keys may be mistaken for the same; for example: a[1], a["1"]. To solve the above problem, you still have to call "indexOf".

// 速度最快， 占空间最多（空间换时间）
function unique2(array){
 var n = {}, r = [], len = array.length, val, type;
  for (var i = 0; i < array.length; i++) {
    val = array[i];
    type = typeof val;
    if (!n[val]) {
      n[val] = [type];
      r.push(val);
    } else if (n[val].indexOf(type) < 0) {
      n[val].push(type);
      r.push(val);
    }
  }
  return r;
}

3. Array subscript judgment method

You still have to call "indexOf", the performance is similar to method 1,

Implementation Idea: If the first occurrence of the i-th item in the current array is not i, it means that the i-th item is repeated and ignored. Otherwise, store the result array.

function unique3(array){
 var n = [array[0]]; //结果数组
 //从第二项开始遍历
 for(var i = 1; i < array.length; i++) {
  //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
  //那么表示第i项是重复的，忽略掉。否则存入结果数组
  if (array.indexOf(array[i]) == i) n.push(array[i]);
 }
 return n;
}

4. Adjacent removal method after sorting

Although the sorting result of the "sort" method of the native array is not very reliable, but in This shortcoming has no effect in deduplication without paying attention to the order.

Implementation idea: Sort the incoming array. After sorting, the same values ​​are adjacent, and then when traversing, only add values ​​that are not duplicates of the previous value to the new array.

// 将相同的值相邻，然后遍历去除重复值
function unique4(array){
 array.sort(); 
 var re=[array[0]];
 for(var i = 1; i < array.length; i++){
  if( array[i] !== re[re.length-1])
  {
   re.push(array[i]);
  }
 }
 return re;
}

5. Optimize traversal array method

comes from foreign blog posts, the implementation code of this method is quite cool;

Implementation idea: Get the rightmost value without duplication and put it into a new array. (When duplicate values ​​are detected, the current loop is terminated and the next round of judgment of the top-level loop is entered)

// 思路：获取没重复的最右一值放入新数组
function unique5(array){
 var r = [];
 for(var i = 0, l = array.length; i < l; i++) {
  for(var j = i + 1; j < l; j++)
   if (array[i] === array[j]) j = ++i;
  r.push(array[i]);
 }
 return r;
}

The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.

Related articles:

Comparison and distinction between Express and Koa2 in nodejs (detailed tutorial)

Closures in js (detailed tutorial )

The singleton mode in JS implements data addition, deletion, modification and query

Use Vue to imitate Toutiao (detailed tutorial)

How to configure eslint for React development

js scope and pre-parsing mechanism (detailed tutorial)

The above is the detailed content of What are the efficient algorithms in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!