数组去重 | soHappy

字符串的indexOf方法查寻

先把数组用join方法拼接成字符串,再通过字符串来查寻重复的字段,这种方法吃力不讨好,很耗性能。

String.indexOf()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function unitArray1(arr) {
var b = ',' + arr.join(',') + ',', //将数组合并成字符串
a = [],
re, ree;
for (var i = 0,len=arr.length; i<len; i++) {
var str = ',' + arr[i] + ','; //把数组单项通过+运算符隐式的转换成字符串
re = b.indexOf(str, 0); //第一次查寻b,得到首次出现str的index值re
ree = b.indexOf(str, re + 1); //第二次查寻b,从re+1开始
if (ree === -1) { //如果第二次查寻的index是-1,及此项是没有有重复的
a.push(arr[i]) ; //向新数组a推送此项
}else{
b=b.replace(str,','); //删除字符串段
}
}
return a;
}

适用性:一般。 如果数组中有undefined和null类型的重复值,那么这些重复值将不会被去重,因为undefined和null没有toString方法,join()方法把他们都转换成了空字符串。
性能:差。使用了数组转换字符串,遍历数组,字符串查寻字段,字符串删除字段。

数组的indexOf方法查寻

此方法最简单明了,直接在数组中查找重复值。

Array.indexOf()
1
2
3
4
5
6
7
function unitArray2(arr){
var a=[];
for(var i=0,len=arr.length;i<len;i++){
if(arr.indexOf(arr[i]) === i) a.push(arr[i]); //如果arr.indexOf(arr[i])不是出现在i的位置,就说明它是一个重复的项。否则就向新数组a添加
}
return a;
}

适用性:差。不会对数组和对象这样的引用类型的数据去重,因为一个引用类型只会等于其自身,所以利用数组的indexOf方法查寻对象和数组类型的值,将永远会返回其自身的index。
性能: 一般。使用了数组遍历,数组查寻。

数组的sort方法

数组的sort方法排序,再比较相邻两个值转换成字符串来比较。

Array.sort()
1
2
3
4
5
6
7
8
9
10
11
12
13
function unitArray4(arr){
arr.sort(); //调用sort方法给数组排序,这是关键。
var a = [];
a.push(arr[0]); //由于数组从第二项开始遍历,所以需要初始化加入第一项。
for(var i=1,len=arr.length; i<len; i++){
var v1 = arr[i] + 'a', //a只是占位符,使用+运算符来转换字符串有个好处就是不怕遇到undefined和null这样的类型。
v2 = arr[i-1] + 'a';
if(v1 != v2){
a.push(arr[i]); //只有相邻两项的字符串值不等的时候给a推送此项。
}
}
return a;
}

适用性:优。经测,这种方法测试能够对各种数据类型数据正确的去重。
性能:较优。sort排序,数组遍历。

对象下标查寻

把数组中的值转换并保存为一个对象的属性名,再通过对象hasOwnProperty方法来查寻是否重复。

Object.hasOwnProperty()
1
2
3
4
5
6
7
8
9
10
11
12
function unitArray3(arr){
var a=[],
o={};
for(var i=0,len=arr.length;i<len;i++){
var v = arr[i];
if(!o.hasOwnProperty(v)) {
o[v]=true; //用o对象下标来查寻,如果已经存在该属性,则跳过,否则加入此属性
a.push(v); //同时向新数组a推送此项。
}
}
return a;
}

适用性:优。经测,这种方法测试能够对各种数据类型数据正确的去重。
性能:优。使用了数组遍历,对象属性查寻。

我用了一个包含1万个随机数字的数组,来做了性能测试.结果,方案1、2、3、4的运行时间依次是:190ms、33ms、9ms、1ms.可见,字符串查寻是很耗性能的,而对象属性查寻性能是杠杠的!

ps:以前从没关系过数组去重这个命题,上次有幸去阿里面试了“资深前端工程师”,此文就缘由自这道考倒我的面试题。
在阿里巴巴西溪园区逛了一圈,究竟是顶尖的互联网企业,园区建筑,园林,雕塑处处体现了独特的阿里文化。
阿里巴巴西溪园区内的雕塑