Summary of javascript array deduplication_javascript skills

Foreword

Recently, in order to change jobs and prepare for an interview, I started to review and review JavaScript-related knowledge. Yesterday afternoon, I thought of the related methods of array deduplication, so I simply compiled a few JavaScript algorithm articles for future use. This series of articles is uncertain. Number, indefinite time, I will write wherever I think, no guarantee of accuracy, no guarantee of high efficiency, just talk about personal understanding, if there are any mistakes, please correct me.

About duplicate removal

Array deduplication is a common algorithm inspection point, and the way to achieve deduplication is nothing more than through uniqueness and non-uniqueness. To put it simply, it means to pick out the unique ones or delete the ones that are not unique. All the following algorithms are blindly named by me, please ignore them.

Loop matching to remove duplicates

As the name suggests, each element in the array is compared with the array storing the element. When encountering non-repeating elements, it is put into a new array until the end of the loop. Since matching also has loops, it can also be called double loop matching. Removing duplicates is the simplest way that everyone can think of.

Implementation code:

var arr=[1,3,4,56,3,7,9,7];
var result=[];
//匹配
function isMatch(array,n){
  for(var i=0;i<array.length;i++){
    if(array[i]==n){
      return true;
    }
  }
  return false;
};
//验证所有元素
function unqiue(array){
  for(var i=0;i<array.length;i++){
    if(!isMatch(result,array[i])){
      result.push(array[i]);
    }
  }
  return result;
};

console.log(unqiue(arr));

Note: There is a bug in the above method. When there are numbers and numerical strings, numbers and numerical strings are not distinguished. Because double equality "==" is used in the matching function isMatch() and the element type is not verified, congruent "===" should actually be used.
The modified code is as follows:

var arr=[1,3,4,56,3,'1',7,9,7];
var result=[];
//匹配
function isMatch(array,n){
  for(var i=0;i<array.length;i++){
    if(array[i]===n){
      return true;
    }
  }
  return false;
};
//验证所有元素
function unqiue(array){
  for(var i=0;i<array.length;i++){
    if(!isMatch(result,array[i])){
      result.push(array[i]);
    }
  }
  return result;
};

console.log(unqiue(arr));

Algorithm advantages and disadvantages:

Advantages:

Simple implementation and intuitive thinking

Disadvantages:

Inefficiency

JSON deduplication/object deduplication/dictionary deduplication

JSON deduplication, simply put, is to use the uniqueness of the Object object key to convert the elements of the array into JSON or the key value of the object. The JSON value stores the index index of the array, and then performs a for in loop on the JSON object and stores it in a new array.

Array, JSON, and {} are all Objects, so this algorithm can be implemented using any one.

Implementation code:

Array mode:

var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
  var cache=[];
  var result=[];
   //将数组元素转为对象的key
  for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
  };
  
  //存储key(实际的数组元素)
  for(key in cache){
    result.push(key);
  };
  
  return result;
}
  
console.log(unqiue(arr));

JSON mode:

var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
  var cache={};
  var result=[];
   //将数组元素转为对象的key
  for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
  };
  
  //存储key(实际的数组元素)
  for(key in cache){
    result.push(key);
  };
  
  return result;
}
  
console.log(unqiue(arr));

Object mode:

var arr=[1,3,4,56,3,'1',7,9,7];
function unqiue(array){
  var cache=new Object();
  var result=[];
   //将数组元素转为对象的key
  for(var i=0;i<array.length;i++){
    cache[array[i]]=i;
  };
  
  //存储key(实际的数组元素)
  for(key in cache){
    result.push(key);
  };
  
  return result;
}
  
console.log(unqiue(arr));

Algorithm advantages and disadvantages:

Advantages:

Simple

Very efficient

Disadvantages:

1. Changed the type of array elements ()
2. There is a bug (nothing more than distinguishing between numbers and numeric strings)

Queue recursive deduplication

I thought about it for a long time last night and thought of using a queue. First sort the array into a queue in ascending or descending order, so that the same elements are in a region, and then match from the end of the queue forward. If the match is successful, delete the end of the queue. , and then the previous element matches the previous element. After the entire matching is completed, the remaining elements are the deduplicated queue.

var arr=[6, 4, 6, 9, '6', 13, 56, 9, ,'11',1, 8, '7', 17, 5, 45, 3, 7];

function unqiue(array){
  //排序数组，形成队列
  array.sort(function(m,n){return m-n;});
  ////排序后，队尾向前对比，如果相同，删除队尾，依次类推
  function loop(Index){
    if(Index>=1){
      if(array[Index]===array[Index-1]){
        arr.splice(Index,1);
      }
      loop(Index-1);
    }
    
  }
  loop(array.length-1);
  return array;
}

console.log(unqiue(arr));

Algorithm advantages and disadvantages:

Advantages:

Higher efficiency

Disadvantages:

Not the most efficient

INDEXOF deduplication method

Determine whether the browser supports indexOf. indexOf is a new method of ecmaScript5. It is not supported by IE8 and below (including IE8, IE8 only supports part of 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; 
} 
}