给数组去除重复项并排序

2009年12月17日

在逛社区的时候看到一个网友发了这样一个帖子：

已知一个装满数的数组，需求是：清除里面的重复项并排序。

1
2
3
4

var baseNumArray=[];
for(var i= 0;i<1000;i++){
    baseNumArray.push(Math.floor(Math.random()*i));
}

这里包含了两个需求，去除重复项和排序。很多人倾向于直接修改原来的数组，我觉得还是保留原来的数组比较好。所以这里扩展的这个方法并不破坏原来的数组，而是返回了一个全新的数组。采用最直观、基础的解决方案就是使用循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/*
 * 扩展Array对象的原型，添加一个cleanNumSort()方法。
 * 提供一个排序方向的参数，true(或默认不填)是升序，flase是降序。
 */
Array.prototype.cleanNumSort = function(bn){
       var clean = [];
       //首先排序
       this.sort(function(a,b){return a-b;});
       //然后执行一个复杂度为O(n)的循环
       for(var i=0;i<this.length;i++){
              if(this[i]==this[i+1]){
                     continue;
              }else{
                     clean.push(this[i]);
              }
       }
       //判断排序的方向
       if(!bn&&arguments.length!=0){clean.reverse();}
       return clean;
}
 
//执行这个方法，返回干净的排序过的新数组。
baseNumArray.cleanNumSort();

如果利用空间整理法，则可以高效的剔除重复数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Array.prototype.cleanNumSortA = function(fn){
       var clean = [];
       //声明了一个仓库数组，用来依靠他的空间和下标进行数据整理
       var depot = [];
       for(var i=0;i<this.length;i++){
               if(depot[this[i]] == undefined){
                      depot[this[i]] = this[i];
               }
       }
       //清理掉无效的项
       for(var i=0,len=depot.length;i<len;i++){
              if(depot[i] != undefined){
                     clean.push(depot[i]);
              }
       }
       if(!bn&&arguments.length!=0){clean.reverse();}
       return clean;
}
baseNumArray.cleanNumSortA();

经过测试，通过空间换时间以及抛弃数组自带的比较低效的sort()方法，清除重复项和排序一次完成，这个新的函数速度要快许多。

鉴于这个需求具有一定的普遍性，值得深入研究一下。想到上面的方法只能针对里面全部是数字的数组，缺乏一定的通用性，如果里面不仅是数字怎么办？如果继续按照正常的思维方式，那就是普通的循环比对，一般我们会这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/*
 * 这里的fn参数和数组默认的sort()方法的参数性质相同，都是排序函数。
 */
Array.prototype.cleanSort = function(fn){
       var clean = [];
       var len = this.length;
       //这里是一个n(n-1)/2次数的循环
       for(var i=0;i<len;i++){
              for(var j=i;j<=len;j++){
                     if(this[i]==this[j+1]){
                            break;
                     }else if(j==len){
                            clean.push(this[i]);
                     }
              }
       }
       //执行数组的排序函数
       if(fn){clean.sort(fn);}else{clean.sort();}
       return clean;
}

如果采用空间整理法，就可以这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Array.prototype.cleanSort= function(fn) {
        var clean = [];
        var depot = {};
        var len = this.length,n = 0;
        for(var i=0;i<len;i++)  {  
                if(depot[this[i]] == undefined) {
                        depot[this[i]] = true;
                }  
       }  
       for(var i in depot) {  
              clean[n++] = i;
       }
       if(fn){clean.sort(fn);}else{clean.sort();}
       return clean;  
}

尽管在通常情况下，后者的速度要快很多。但是采用后者的问题也是显而易见的：数组中的元素只能是数字或者字符串才适用，如果数组本身是一个多维数组或者数组的值是对象的时候就无法使用了。

所以，什么时候需要空间整理法是要看具体的需求而定的。

标签： , , ,
发布在 Javascript, 技术相关 | 没有评论 »