请给 Array 本地对象增加一个原型方法,它的用途是删除数组条目中重复的条目(可能有多个),
返回值是一个包含被删除的重复条目的新数组。

Lazy 兄弟给出了它自己的解法,而我个人认为这样的解法算法上还有需要改进的地方。正如回复中 fdcn 兄弟所说,如果将数组:[1, 2, 3, 3, null, null, 2] 带入 Lazy 兄的函数,那么按照循环判断条件就会退出,导致数组之后的元素就不会判断了。

下面给出我的解决方法:

Array.prototype.uniq = function(){
    var tmp    = new Array;
    var length = this.length;

    for(var i = 0; i < length; i++) {
        var push = true;
        var item = this[i];

        for(var j = i + 1; j < length; j++) {
            if(this[j] == item) {
                push = false;
            }
        }

        if(push == true) {
            tmp.push(item)
        }
    }

    return tmp;
}

Lazy 兄弟也说到每次循环都将重新计算 length 会有开销,那么我将 legth 定义为一个常量,原数组为「只读」,那么 length 相对不变,就不要重复计算了。然后再定义一个数组往里面扔「垃圾」。

数组嵌套循环并不遍历原数组的每一个元素,仅判断剩余没有出现的值。最后获得一个是否 push 的布尔值,然后跳出循环判断是否插入。

最后,欢迎大家交流讨论。


更新,和 Lazy 兄弟讨论后,我发现此函数写得也不是非常的严谨。因为它没有修改原函数的元素,于是我又作了如下的修改:

Array.prototype.uniq = function(){
    var tmp    = new Array;
    var length = this.length;

    for(var i = 0; i < length; i++) {
        var push = true;
        var item = this[i];

        for(var j = i + 1; j < length; j++) {
            if(this[j] == item) {
                push = false;
            }
        }

        if(push) {
            tmp.push(item)
        }
    }

    this.length = tmp.length;
    for (var i = 0; i < tmp.length; i++) {
        this[i] = tmp[i];
    }

    return tmp;
}

但这样又出现了一个问题,就是重复赋值会不会增加时间长度。因为我是在取出来了以后再做一次循环重新赋值给原数组。按照我这样的写法实现已经没有问题,但是效率可能需要进一步的调整。

继续改进ing


不好意思,再次更新。根据上述的问题,我重新优化了下算法,并将 Lazy 兄弟的「思想」加了进来,于是就有如下的代码了:

Array.prototype.uniq = function(){
    var i = 0, j = 0;
    while (undefined !== this[i]){
        j = i + 1;
        while(undefined !== this[j]){
            if (this[i] === this[j]) {
               this.splice(j, 1);
            }
            ++j;
        }

        ++i;
    }

    return this;
}

是的,非常的短,不过却能完成题目所给的要求了。这个相对我以前的函数,有一个好处就是没有生成另外的一个数组。而且也没有像第二个函数这样的重复赋值。

嗯,我想目前这个样子已经能满足题目的要求了。