浅谈Javascript数组去重

刚好前天面试的时候面试官问到了数组去重的问题,当时有点语塞只想到用了两个循环检测(其实模模糊糊想到了hash的方法做但是由于记得不清不敢说= =!),思路是检测是否有元素重复,然后将只出现一次的元素推入到新数组中,然后返回新数组。然后面试官又问这种方法的时间效率,于是黑线了。so这两天看了一下相关的文章,在这里也总结一下javascript数组去重的方法。

两层循环检测重复元素法

首先,介绍一下大家都会想到的两层循环的demo,如下例:

function distinct(arr) { var ret = [], length = arr.length; for(var i = 0;i < length; i++){ for(j = i+1; j<length;j++){ if(arr[i] === arr[j]){ j = ++i; } } ret.push(arr[i]); } return ret; } var arra = [1,2,3,4,4,1,1,2,1,1,1]; distinct(arra);

如上的代码实现是轻松易得的,思路如下:

  1. 首先外层循环比遍历整个数组
  2. 内层循环匹配是否有值重复 a.如判断有相同元素则自增i变量,跳出i的循环 b.如判断无时则将无相等值的元素推入到ret数组中
    3.返回ret。

优点:便捷易懂,大多数程序员能想到。
缺点:很明显时间消耗太高,两层循环时间消耗太多,时间的消耗为O(n^2^),在进行大量数据处理时会消耗大量资源。而且该方法无法处理字符和数组,如下例:

var arr = [1,23,4,5,6,7,’1',22,3,1,2]; distinct(arr);

所以我们可以开始考虑一些别的方法优化数组去重:

sort重排数组去除重复元素索引法

这种方法就是先讲原数组使用sort方法将数组重排,以得到将相同元素为相邻位的一个新数组。该方法如下:

function distinct(arr){ var self = arr; list = self.concat().sort(); list.sort(function(a, b){ if(a === b){ var ind = self.indexOf(a); self.splice(ind, 1); } }); return self; } var arra = [1,2,3,3,1,1,1,’1']; distinct(arra);

同样的,在使用这种方法的重排的时候,仍然会有一定的资源消耗,在sort()函数中回调函数是使用的冒泡排序,而冒泡排序的效率并不高。但是使用这种方法的效率仍然比上一种方法的效率高,因为在此例中只出现了一次循环遍历。

优点:程序简洁,效率较高。
缺点:1.仍然无法解决数字1和字符’1’的去除。2.依赖indexOf方法,我们知道在IE6~8中并未支持indexOf()方法。
所以我们还要做一些兼容性的处理。如下:

var indexOf = [].indexOf ? function indexOf(arr, item){ return arr.indexOf(item); }: function indexOf(arr, item){ for(var i = 0; i < arr.length; i++){ if(arr[i] === item){ retrun i; } } return -1; } function distinct(arr){ var self = arr; list = self.concat().sort(); list.sort(function(a, b){ if(a === b){ var ind = self.indexOf(arr, a); self.splice(ind, 1); } }); return self; }

将数组元素值存为对象的属性

function distinct(arr) { var ret = [], json = {}, length = arr.length; for(var i = 0; i < length; i++){ var val = arr[i]; if(!json[val]){ json[val] = 1; ret.push(val); } } return ret; } var arra = [1,2,3,5,7,1,2,’1'];

以上方法更加的简洁,而且也能在原来的基础上区分字符‘1’和数字1的区别。
在此例中思路如下:
1.循环遍历每一个元素
2.检测在json对象中是否含遍历到的元素的值 a: 如果是则跳过 b: 如果否存入json对象中该属性名的值设为1
3.将存入对象了元素的值推入到新数组中,返回新数组。

总结,其实数组去重无非就是判断一个元素在数组中是否有重复的值。优化也是一直改变判定元素是否重复的一些技巧,如例1中是遍历数组,例2是重排数组获得索引,例3则别出心裁将元素的值作为对象的属性。

参考自: 从 JavaScript 数组去重谈性能优化 也谈javascript数组去重 js数组去重

同步于个人博客:http://penxx.pw

javascript 数组 array 去重 distinct unique


Originally published at penxx.pw on May 19, 2014.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.