数组去重——一道前端校招试题

很多校招题是没有严格的标准答案的，只有知识点，只要几个关键点能答上来，不管程序是否真的能跑通，都可以拿分的。比如最常见的一道题：







试题：






有这样一个数组，成员都是数字，例如



var a = [1,2,3,4,5,2,3,4,6,7,8];



请实现a.distinct()方法，用来给数组a去掉重复值，要求对Array的原型进行扩展方法，并尽可能做到效率最优。






Array.prototype.distinct = function(){
    var self = this;
    var _a = this.concat().sort();
    _a.sort(function(a,b){
        if(a == b){
            var n = self.indexOf(a);
            self.splice(n,1);
        }
    });
    return self;
};

考察点：



1，考察应试者是否理解原型链



2，考察应试者是否由意识的控制算法的时间复杂度，了解应试者对专业课知识的掌握程度



3，考察应试者对js数组函数的了解程度




答案1：
Array.prototype.distinct = function(){
    var a = [],b=[],oa = this.concat();
    for(var i = 1;i<oa.length;i++){
        for(var j = 0;j<i;j++){
            if(b.indexOf(j)>-1)continue;
            if(oa[j] == oa[ i]){
                b.push(j);
            }
        }
    }
    this.splice(0,this.length);
    for(var i = 0;i<oa.length;i++){
        if(b.indexOf(i)>-1)continue;
        this.push(oa[i ]);
    }
    return this;
};

答案2：
Array.prototype.distinct = function(){
    for(var i = 0;i<this.length;i++){
        var n = this[i ];
        this.splice(i,1,null);
        if(this.indexOf(n) < 0){
            this.splice(i,1,n);//不存在重复
        }else{
            this.splice(i,1);//存在重复
        }
    }
    return this;
};
答案3：

Array.prototype.distinct = function(){
    var self = this;
    var _a = this.concat().sort();
    _a.sort(function(a,b){
        if(a == b){
            var n = self.indexOf(a);
            self.splice(n,1);
        }
    });
    return self;
};





得分点：

1，应试者起码应该自觉通过Array.prototype.distince来实现函数，若没有这样做，则扣分50%

2，应试者起码会给出答案1，得分30%，如果没有使用splice和concate，扣分20%

3，给出答案2的，得分80%，算法复杂度控制在O(n)

4，给出答案3的，得满分，算法复杂度控制在O(1)

 

评论

1 楼 hyspace 2013-12-17  

别逗了，最后一个算法根本不是最优的，sort(function)本身的复杂度就是n*logn，所以加起来也就是2nlogn
如果是先sort之后的数组，可以一次循环就完成排重，总的时间复杂度最优是n*logn+n