- 更新的算法请参见: http://www.gracecode.com/posts/338/ :
请给 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;
}
是的,非常的短,不过却能完成题目所给的要求了。这个相对我以前的函数,有一个好处就是没有生成另外的一个数组。而且也没有像第二个函数这样的重复赋值。
嗯,我想目前这个样子已经能满足题目的要求了。