数组去重的几种算法

第⼀种算法：算法思想：

1、构建⼀个新数组，新数组包含⼀个元素，元素值为⽬标数组的⼀个值；2、从⽬标数组的第⼆个元素开始遍历，依次取出每⼀个元素；

3、将取出的元素与新数组⾥⾯的所有元素进⾏⽐较，如果没有出现，则将该元素添加到新数组中，如果出现，则处理下⼀个⽬标数组的元素；4、⽬标数组的所有元素均已处理完。

1 Array.prototype.deleteRepeat1=function (){

2 //构建⼀个新数组，存放结果,⾸先给newArray⼀个初值，初值为调⽤该函数的数组的第⼀个值即this[0] 3 var newArray=[this[0]];

4 //for循环，每次从原数组中取出⼀个元素 5 //⽤取出的元素循环与结果数组⽐较 6 for(var i=1;i7 // 添加⼀个标记，⽤于标记当前元素是否在newArray中出现过 8 var repeat=false;

9 for(var j=0,len=newArray.length;j16 //如果原数组中没有该元素，则存放到结果数组中17 if(!repeat){

18 newArray.push(this[i]);19 }20 }

21 return newArray;22 }

23 var array=[1,1,2,2,2,3,3,4,5,6,6,6,6];24 array.deleteRepeat();//1,2,3,4,5,6View Code

对上⾯试算法的改进：

利⽤forEach，indexOf⽅法替代上述的循环和检测：

1 Array.prototype.deleteRepeat1=function (){ 2 var newArray=[];

3 // index是⽬标数组中的每⼀个元素 4 this.forEach(function(index){

5 // indexOf⽅法返回index在newArray中出现的位置，如果没有出现则返回-1 6 if(newArray.indexOf(index) == -1){ 7 newArray.push(index); 8 } 9 });

10 return newArray;11 }View Code

但是在IE9+以下并不⽀持forEach函数；可以重写forEach 函数实现兼容。第⼆种算法：算法思想：

1、对⽬标数组进⾏排序；

2、遍历⽬标数组，检测数组中的第 i 个元素与结果数组中最后⼀个元素是否相同，如果不同，则将该元素添加到结果数组中；

1 Array.prototype.deleteRepeat2=function (){ 2 // ⾸先对⽬标数组进⾏排序 3 this.sort();

4 var newArray=[];

5 // index是⽬标数组中的每⼀个元素 6 for(var i=0,len=this.length;i7 // 将this[i]与newArray中的最后⼀个元素⽐较，因为已经排过序，相同的元素肯定在相同的位置了 8 if(this[i] !== newArray[newArray.length-1]){ 9 newArray.push(this[i]);10 }11 }

12 return newArray;13 }View Code

这种算法的优缺点：

去重后的数组是排过序的，⽽且⽆法区分与数字相同的数字字符 ⽐如： “1” 和 1；第三种算法：算法思想：

1、创建⼀个新数组和新对象；

2、遍历⽬标数组中的每⼀个元素，将该元素与对象进⾏⽐对，如果不重复则添加到结果数组中，同时将该元素的值作为对象的属性，并将该属性值设为1；

1 Array.prototype.deleteRepeat2=function (){ 2 var newArray =[]; 3 // 创建⼀个空对象 4 var object = {};

5 // 每次取出⼀个元素，与对象进⾏⽐对，如果这个元素不重复，则添加到结果数组中，同时把这个元素的内存作为对象的⼀个属性并存⼊对象中 6 for(var i=0,len=this.length;i9 object[typeof(this[i]) + this[i]]=1;10 }11 }

12 return newArray;13 }View Code

这种算法的效果最好，速度最快。但是占⽤内存⼤。对这个算法的理解：

这⾥的对象也可以换成⼀个数组，每次将不重复的元素作为数组的索引，然后将该索引值设为1，下次再出现时如果array[element]==1;说明此element已经出现过，是重复的。第四种算法：算法思想：

1、创建⼀个新数组保存结果；

2、对⽬标数组进⾏排序，将⽬标数组中的第⼀个元素存⼊结果数组中；

3、处理⽬标数组的第⼆个元素，如果这个元素和它前⾯的元素不同，说明是不重复，则添加到结果数组中。

1 Array.prototype.deleteRepeat3=function (){ 2 var newArray =[this[0]]; 3 this.sort();

4 for(var i=1;i5 ⽐较当前元素和前⼀个元素是否相同，如果重复，排序后，相同的会在⼀起。 6 if(this[i] !== this[i-1]){ 7 newArray.push(this[i]); 8 } 9 }

10 return newArray;11 }View Code第五种算法：算法思想：

1、利⽤数组的reduce⽅法，对数组中的每⼀个元素进⾏处理

1 Array.prototype.deleteRepeat3=function (){

2 // 通过数组的reduce⽅法，对数组中的每⼀个元素进⾏处理，原理都⼀样，只是使⽤了不同的⽅法3 return this.reduce(function(newArray,index){4 if(newArray.indexOf(index)<0){5 newArray.push(index);6 }

7 return newArray;8 },[]);9 }View Code第六种算法：算法思想：

1、和上⾯相同，不过是使⽤了filter⽅法

1 Array.prototype.deleteRepeat3=function (){2 var newArray=[];

3 newArray=this.filter(function(ele,i,arr) {4 return arr.indexOf(ele) === i;5 });

6 return newArray;7 }View Code第七种算法：

这种是利⽤ES6去重，相对来说更为简单

1 //es6

2 function deleteRepeat(arr){ 3 const seen=new Map(){

4 return arr.filter((a)=>!seen.has(a)&&seen.set(a,1)); 5 } 6 } 7 //or

8 function deleteRepeat2(arr){

9 return Array.form(new Set(arr))10 }View Code