Detailed introduction to 5 efficient algorithm sample codes for deleting duplicate elements from arrays in JavaScript

I have been preparing for interviews for a while, so the blog has not been updated for a long time; now that I have reviewed all the basic knowledge points, I will share some common questions about interviews:

Go to a regular Internet company for a written test, There is a high probability that you will encounter Use javascript to implement array deduplication coding problems during the interview: such as: Meizu written test questions;

This blog post summarizes 5 types of how to implement array deduplication in js method, and attach the demo and source code.

1. Array traversal method

The simplest method to remove duplicates, Implementation ideas: Create a new array and traverse the incoming Array, If the value is not in the new array, add it to the new array; Notes: 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 Some codes that are compatible with lower version browsers, 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, 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, add the key to the object and put in the 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.

You still have to call "indexOf", the performance is similar to method 1, Implementation idea: If the i-th item of the current array is the first time in the current array If the position that appears is not i, it means that the i-th item is repeated and is 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.

Although the sorting result of the "sort" method of the native array is not very reliable, this shortcoming has no impact in deduplication that does not pay 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. Optimizing array traversal method

comes from foreign blog posts. The implementation code of this method is quite cool;Implementation ideas: Obtain the rightmost value without repetition 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 the detailed content of Detailed introduction to 5 efficient algorithm sample codes for deleting duplicate elements from arrays in JavaScript. For more information, please follow other related articles on the PHP Chinese website!