javascript--数组去重
卧斋 2016-06-17
总共想出了三种算法来实现这个目的：
Array.prototype.unique1=function()
{
varn=[];//一个新的临时数组
for(vari=0;i<this.length;i++)//遍历当前数组
{
//如果当前数组的第i已经保存进了临时数组，那么跳过，
//否则把当前项push到临时数组里面
if(n.indexOf(this[i])==-1)n.push(this[i]);
}
returnn;
}
Array.prototype.unique2=function()
{
varn={},r=[];//n为hash表，r为临时数组
for(vari=0;i<this.length;i++)//遍历当前数组
{
if(!n[this[i]])//如果hash表中没有当前项
{
n[this[i]]=true;//存入hash表
r.push(this[i]);//把当前数组的当前项push到临时数组里面
}
}
returnr;
}
Array.prototype.unique3=function()
{
varn=[this[0]];//结果数组
for(vari=1;i<this.length;i++)//从第二项开始遍历
{
//如果当前数组的第i项在当前数组中第一次出现的位置不是i，
//那么表示第i项是重复的，忽略掉。否则存入结果数组
if(this.indexOf(this[i])==i)n.push(this[i]);
}
returnn;
}
其中第1种和第3种方法都用到了数组的indexOf方法。此方法的目的是寻找存入参数在数组中第一次出现的位置。很显然，js引擎在实现这个方法的时候会遍历数组直到找到目标为止。所以此函数会浪费掉很多时间。而第2中方法用的是hash表。把已经出现过的通过下标的形式存入一个object内。下标的引用要比用indexOf搜索数组快的多。
为了判断这三种方法的效率如何，我做了一个测试程序，生成一个10000长度的随机数组成的数组，然后分别用几个方法来测试执行时间。结果表明第二种方法远远快于其他两种方法。但是内存占用方面应该第二种方法比较多，因为多了一个hash表。这就是所谓的空间换时间。就是这个测试页面，你也可以去看看。
2010年10月7日更新:
根据hpl大牛的思路，我写了第四种方法：
Array.prototype.unique4=function()
{
this.sort();
varre=[this[0]];
for(vari=1;i<this.length;i++)
{
if(this[i]!==re[re.length-1])
{
re.push(this[i]);
}
}
returnre;
}
这个方法的思路是先把数组排序，然后比较相邻的两个值。排序的时候用的JS原生的sort方法，JS引擎内部应该是用的快速排序吧。最终测试的结果是此方法运行时间平均是第二种方法的三倍左右，不过比第一种和第三种方法快了不少。
jsjquery去除数组中的重复元素
第一种：$.unique()
第二种：
for(vari=0,len=totalArray_line.length;i<len;i++)
{
!RegExp(totalArray_line[i],"g").test(resultArray_line.join(","))&&(resultArray_line.push(totalArray_line[i]));
}-----解决了V0.2版本问题
第三种（来自网络博客总结）：
jQuery数组处理详解(含实例演示)
PostedbyMr.Thinkon11/26/2010分类于@jQuery
jQuery的数组处理,便捷,功能齐全.最近的项目中用到的比较多,深感实用,一步到位的封装了很多原生js数组不能企及的功能.最近时间紧迫,今天抽了些时间回过头来看jQuery中文文档中对数组的介绍,顺便对jQuery数组做个总结.温故,知新.
强烈建议你打开DEMO演示后再看下面的详解:点此查看DEMO
1.$.each(array,[callback])遍历[常用]
解释:不同于例遍jQuery对象的$.each()方法,此方法可用于例遍任何对象(不仅仅是数组哦~).回调函数拥有两个参数：第一个为对象的成员或数组的索引,第二个为对应变量或内容.如果需要退出each循环可使回调函数返回false,其它返回值将被忽略.
each遍历,相信都不陌生,在平常的事件处理中,是for循环的变体,但比for循环强大.在数组中,它可以轻松的攻取数组索引及对应的值.例:
1var_mozi=['墨家','墨子','墨翟','兼爱非攻','尚同尚贤'];//本文所用到的数组,下同
2$.each(_mozi,function(key,val){
3//回调函数有两个参数,第一个是元素索引,第二个为当前值
4alert('_mozi数组中,索引:'+key+'对应的值为:'+val);
5});
相对于原生的for..in,each更强壮一点.for..in也可以遍历数组,并返回对应索引,但值是需要通过arrName[key]来获取;
2.$.grep(array,callback,[invert])过滤数组[常用]
解释:使用过滤函数过滤数组元素.此函数至少传递两个参数(第三个参数为true或false,对过滤函数返回值取反,个人觉得用处不大):待过滤数组和过滤函数.过滤函数必须返回true以保留元素或false以删除元素.另外,过滤函数还可以是可设置为一个字条串(个人不推荐,欲了解自行查阅);
01$.grep(_mozi,function(val,key){
02//过滤函数有两个参数,第一个为当前元素,第二个为元素索引
03if(val=='墨子'){
04alert('数组值为墨子的下标是:'+key);
05}
06});
07
08var_moziGt1=$.grep(_mozi,function(val,key){
09returnkey>1;
10});
11alert('_mozi数组中索引值大于1的元素为:'+_moziGt1);
12
13var_moziLt1=$.grep(_mozi,function(val,key){
14returnkey>1;
15},true);
16//此处传入了第三个可靠参数,对过滤函数中的返回值取反
17alert('_mozi数组中索引值小于等于1的元素为:'+_moziLt1);
3.$.map(array,[callback])按给定条件转换数组[一般]
解释:作为参数的转换函数会为每个数组元素调用,而且会给这个转换函数传递一个表示被转换的元素作为参数.转换函数可以返回转换后的值、null(删除数组中的项目)或一个包含值的数组,并扩展至原始数组中.
这个是个很强大的方法,但并不常用.它可以根据特定条件,更新数组元素值,或根据原值扩展一个新的副本元素.
01var_mapArrA=$.map(_mozi,function(val){
02returnval+'[新加]';
03});
04var_mapArrB=$.map(_mozi,function(val){
05returnval=='墨子'?'[只给墨子加]'+val:val;
06});
07var_mapArrC=$.map(_mozi,function(val){
08//为数组元素扩展一个新元素
09return[val,(val+'[扩展]')];
10});
11alert('在每个元素后面加\'[新加]\'字符后的数组为:'+_mapArrA);
12alert('只给元素墨子添加字符后的数组为:'+_mapArrB);
13alert('为原数组中每个元素,扩展一个添加字符\'[新加]\'的元素,返回的数组为'+_mapArrC);
4.$.inArray(val,array)判断值是否存在于数组中[常用]
解释:确定第一个参数在数组中的位置,从0开始计数(如果没有找到则返回-1).
记得indexOf()方法了吗?indexOf()返回字符串的首次出现位置,而$.inArray()返回的是传入参数在数组中的位置,同样的,如果找到的,返回的是一个大于或等于0的值,若未找到则返回-1.现在,知道怎么用了吧.有了它,判断某个值是否存在于数组中,就变得轻而易举了.
1var_exist=$.inArray('墨子',_mozi);
2var_inexistence=$.inArray('卫鞅',_mozi)
3if(_exist>=0){
4alert('墨子存在于数组_mozi中,其在数组中索引值是:'+_exist);
5}
6if(_inexistence<0){
7alert('卫鞅不存在于数组_mozi中!,返回值为:'+_inexistence+'!');
8}
5.$.merge(first,second)合并两个数组[一般]
解释:返回的结果会修改第一个数组的内容——第一个数组的元素后面跟着第二个数组的元素.
这个方法是用jQuery的方法替代原生concat()方法,但功能并没有concat()强大,concat()可以同时合并多个数组.
1//原生concat()可能比它还简洁点
2_moziNew=$.merge(_mozi,['鬼谷子','商鞅','孙膑','庞涓','苏秦','张仪'])
3alert('合并后新数组长度为:'+_moziNew.length+'.其值为:'+_moziNew);
6.$.unique(array)过滤数组中重复元素[不常用]
解释:删除数组中重复元素.只处理删除DOM元素数组,而不能处理字符串或者数字数组.
第一次看到这个方法,觉得这是个很便捷的方法,可以过滤重复,哈,多完美,但仔细一看,仅限处理DOM元素.功能8折了.所以,我给它定义成了一个不常用的元素,至少,我用jQuery以来没用到过它.
1var_h2Arr=$.makeArray(h2obj);
2//将数组_h2Arr重复一次
3_h2Arr=$.merge(_h2Arr,_h2Arr);
4var_curLen=_h2Arr.length;
5_h2Arr=$.unique(_h2Arr);
6var_newLen=_h2Arr.length;
7alert('数组_h2Arr原长度值为:'+_curLen+',过滤后为:'+_newLen
8+'.共过滤'+(_curLen-_newLen)+'个重复元素')
7.$.makeArray(obj)将类数组对象转换为数组[不常用]
解释:将类数组对象转换为数组对象,类数组对象有length属性,其成员索引为0至length-1.
这是个多余的方法,无所不能的$本来就包含了这个功能.jQuery官网上解释的非常模糊.其实,它就是将某个类数组对象(比如用getElementsByTagName获取的元素对象集合)转换成数组对象.
var_makeArr=$.makeArray(h2obj);
alert('h2元素对象集合的数据类型转换为:'+_makeArr.constructor.name);//输出Array
8.$(dom).toArray()将所有DOM元素恢复成数组[不常用]
解释:把jQuery集合中所有DOM元素恢复成一个数组;
并不常用的方法,个人甚至觉得它和$.makeArray一样多余.
var_toArr=$('h2').toArray();
alert('h2元素集合恢复后的数据类型是:'+_toArr.constructor.name);
第四种：
<script>
/**
*uniquethearray
*@param{Array}arrayarraytounique
*@return{Array}uniquedarray,notechangeparameter
*/
functionundulpicate(array){
for(vari=0;i<array.length;i++){
for(varj=i+1;j<array.length;j++){
//注意===
if(array[i]===array[j]){
array.splice(j,1);
j--;
}
}
}
returnarray;
}
//定义测试用的数组
vararray1=["2013-06-0600","2013-06-0601","2013-06-0602","2013-06-0603","2013-06-0604","2013-06-0605","2013-06-0605","2013-06-0606","2013-06-0607","2013-06-0607","2013-06-0608"];
//打印原始数组
document.write(array1);
document.write("<br/>");
//去重
array1=undulpicate(array1);
//打印去重后的数组
document.write(array1);
</script>
jQuery.unique(array)：删除数组中重复元素。
这个函数的参数array是jquery对象数组，对于基本数据类型的数组没有去重的功能。
对于基本数据类型的去重，可以使用对unique修改后的函数：
(function($){
$.extend($,{
arrunique:function(array){
varret=[],done={};
try{
for(vari=0,length=array.length;i<length;i++){
vartmp=array[i];//jQuery源码：varid=jQuery.data(array[i]);
if(!done[tmp]){
done[tmp]=true;
ret.push(tmp);
}
}
}catch(e){
ret=array;
}
returnret;
}
});
})(jQuery);
如注释所说，该函数被用来unqiue基本数据类型，对于object对象是被判断为相同的，即{},newfunction()这种对象只有第一个被分析的对象会被保留。以后的版本会做对这些对象的判断。
varyearArray=newArray(2009,2009,2010,2010,2009,2010);
$.unique(yearArray);
alert(yearArray);//2009,2010,2009,2010
需要先排序：
varyearArray=newArray(2009,2009,2010,2010,2009,2010);
$.unique(yearArray<strong>.sort()</strong>);
alert(yearArray);//2009,2010
$.unique()函数通过搜索的数组对象，排序数组，并移除任何重复的节点。如果一个节点和已经在数组中的节点完全相同，那么它被认为是重复的;两个不同的节点具有相同的属性是被认为不重复的。此功能只适用于普通的JavaScriptDOM元素的数组，主要是jQuery内部使用。你可能永远都不需要使用它。
一.对象深拷贝：
对应的浅拷贝，对象是通过地址指向来获得引用的，所以单纯的用一个新对象指向源对象就是浅拷贝，对新对象的操作同样会影响的源对象。好比小明有个U盘，里面装有一些资料，一天，小红也需要这个U盘里的资料，于是拿过来改了里面的资料，结果小明再用时，里面资料就变了，因为两个人用的其实是同一个u盘嘛...如下：
1
2
3
4
5
varobj={a:'a'};
varobj1=obj;
obj.a='a1';
alert(obj.a);
alert(obj1.a);
运行
那么怎么样才能资料各自私有而不影响对方呢，显而易见嘛，让小红也去买个u盘，并把资料也拷一份到她的u盘里，各用个的就行了。于是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
functionclone(myObj)
{
if(typeof(myObj)!='object'||myObj==null)returnmyObj;
varmyNewObj=newObject();
for(variinmyObj)myNewObj[i]=clone(myObj[i]);//递归调用,当对象中又有对象时
returnmyNewObj;
}
varobj={a:'a'};
varobj1=obj;
varobj2=clone(obj);
obj.a='a1';
alert(obj.a);
alert(obj1.a);
alert(obj2.a);
运行
至此，区别也很明显了，obj1浅拷贝由于是访的同一个对象，故改变源对象obj，新对象obj1也随之改变。而深拷贝obj2是新建了一个对象实例，与源对象obj互不干扰。
二.关于数组去重
网上很流行一种解法，如下：
1
2
3
4
5
6
7
8
9
10
Array.prototype.filter=function(){
for(vari=0,temp={},result=[],ci;ci=this[i++];){
if(temp[ci])continue;
temp[ci]=1;
result.push(ci);
}
returnresult;
}
varaa=['1','2','3','1','2'];
alert(aa.filter());
运行
它其实是用了对象的特性，把每个数组元素当做一个对象的属性来判断是否存在，这样做有个好处是不用二次遍历数组。然而，乍一看结果没问题，可是一旦数组里有了number，布尔值，对象等作为元素的时候，就会发现问题了。
原因在于：对象则要求其属性值必须为字符串，如果提供给对象的属性不是字符串，那么则会自动调用toString方法转化为字符串形式，于是，严格来讲，这种方法只能在数组元素全为字符串时才成立
我们再看看jquery的源码是怎么实现数组去重的方法的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unique:function(array){
varret=[],done={};
try{
for(vari=0,length=array.length;i<length;i++){
varid=jQuery.data(array[i]);
if(!done[id]){
done[id]=true;
ret.push(array[i]);
}
}
}catch(e){
ret=array;
}
returnret;
},
乍一看，其实思路跟我上面说的方法是一样的，可是别忘了很重要的一点，varid=jQuery.data(array[i]);这一句，其实是把每个数组元素都转换成了节点数组再做的判断。
所以，如果把安全性放在首位，效率次之的话，数组去重还是应该老老实实二次遍历数组，如下：
1
2
3
4
5
6
7
8
9
10
11
12
functionundulpicate(array){
for(vari=0;i<array.length;i++){
for(varj=i+1;j<array.length;j++){
//注意===
if(array[i]===array[j]){
array.splice(j,1);
j--;
}
}
}
returnarray;
}
当然，如果能确定数组元素类型，大可不必这样做，毕竟二次遍历在数据量大的时候是个不小的消
数组去重，判断数组、对象中的内容是否相同等等，在接下来的文章中使用js来简单实现下，感兴趣的朋友不要错过。
/*
*数组元素去重
*/
if(typeofArray.prototype.distinct!="function"){
Array.prototype.distinct=function(){
this.sort();
for(vari=0;i<this.length-1;i++){
if($.isPlainObject(this[i])&&$.isPlainObject(this[i+1])){
if(o2o(this[i],this[i+1])){
this.splice(i,1);
}
}elseif($.isArray(this[i])&&$.isArray(this[i+1])){
if(a2a(this[i],this[i+1])){
this.splice(i,1);
}
}elseif(this[i]===this[i+1]){
this.splice(i,1);
}
}
}
}
/*
*比较对象是否相同
*/
functiono2o(o1,o2){
if(!($.isPlainObject(o1)&&$.isPlainObject(o2))){
returnfalse;
}
vark1k2=[],k1=[],k2=[];
$.each(o1,function(k,v){
k1.push(k);
});
$.each(o2,function(k,v){
k2.push(k);
});
if(k1.length!=k2.length){
returnfalse;
}
k1k2=k1;
k1k2=k1k2.concat(k2);
k1k2.distinct();
if(k1.length!=k1k2.length||k2.length!=k1k2.length){
returnfalse;
}
varflag=true;
$.each(k1k2,function(i,v){
varv1=o1[v];
varv2=o2[v];
if(typeofv1!=typeofv2){
flag=false;
}else{
if($.isPlainObject(v1)&&$.isPlainObject(v2)){//recursion
flag=o2o(v1,v2);
if(!flag){
returnfalse;
}
}elseif($.isArray(v1)&&$.isArray(v2)){
flag=a2a(v1,v2);
if(!flag){
returnfalse;
}
}else{
if(v1!==v2){
flag=false;
}
}
}
});
returnflag;
}
/*
*比较数组是否完全相同
*/www.jbxue.com
functiona2a(a1,a2){
if(!($.isArray(a1)&&$.isArray(a2))){
returnfalse;
}
if(a1.length!=a2.length){
returnfalse;
}
a1.sort();
a2.sort();
for(vari=0;i<a1.length;i++){
if(typeofa1[i]!=typeofa2[i]){
returnfalse;
}
if($.isPlainObject(a1[i])&&$.isPlainObject(a2[i])){
varretVal=o2o(a1[i],a2[i]);
if(!retVal){
returnfalse;
}
}elseif($.isArray(a1[i])&&$.isArray(a2[i])){//recursion
if(!a2a(a1[i],a2[i])){
returnfalse;
}
}elseif(a1[i]!==a2[i]){
returnfalse;
}
}
returntrue;
}
