浅谈Javascript数组去重
javascript 数组 array 去重 distinct unique
刚好前天面试的时候面试官问到了数组去重的问题，当时有点语塞只想到用了两个循环检测（其实模模糊糊想到了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); //返回[3,4,2,1]
如上的代码实现是轻松易得的，思路如下：
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); //返回[23, 4, 5, 6, 7, "1", 22, 3, 1, 2]
所以我们可以开始考虑一些别的方法优化数组去重：
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); //返回的数组为[2,3,1,'1']
同样的，在使用这种方法的重排的时候，仍然会有一定的资源消耗，在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数组去重
浅谈PHP程序员如何修炼？
浅谈HTML5和HTML4之间的不同
浅谈H5的data-*中容易被忽略的一个小问题
浅谈Javascript中Promise对象的实现
浅谈PHP组件、框架以及Composer
浅谈HTTP的连接管理
PHP Foreach 循环教程
浅谈php中线程安全和非线程安全的不同
前端性能优化（JavaScript篇）