JavaScript 数组的 uniq 方法
来自某个nb招聘的题目：
请给Array本地对象增加一个原型方法，它的用途是删除数组条目中重复的条目(可能有多个)，返回值是一个包含被删除的重复条目的新数组。这是我的答案：
新解
Array.prototype.uniq = function(){
var resultArr = [],
returnArr = [],
i = 1,
origLen = this.length,
resultLen;
function include(arr, value){
for (var i=0, n=arr.length; i<n; ++i){
if (arr[i] === value){
return true;
}
}
return false;
}
resultArr.push(this[0]);
for (i; i<origLen; ++i){
if (include(resultArr, this[i])){
returnArr.push(this[i]);
} else {
resultArr.push(this[i]);
}
}
resultLen = resultArr.length;
this.length = resultLen;
for (i=0; i<resultLen; ++i){
this[i] = resultArr[i];
}
return returnArr;
}这种解法在整个过程对原有数组的改变只有两次，效率比其他两种高了2个数量级左右！可在此测试三种解法的性能。
旧解
以下至“关于测试案例”之间皆为旧文，若阅读不顺，忽略之。
Array.prototype.uniq_slow = function(){
var ret = [],
i = 0,
j = 0;
while (undefined !== this[i]){
j = i + 1;
while(undefined !== this[j]){
if (this[i] === this[j]){
ret.push(this.splice(j, 1)[0]);
} else {
++j;
}
}
++i;
}
return ret;
}感谢猫仔提示，这道题目很容易让人产生误读。看清了题目后更新了。
为何用 while 而不是 for? 因为这个数组总是在变化，每次循环都得重新计算 length. 按理说，使用 while 效率会更高，尤其数组很大的时候。
欢迎大家交流讨论。
感谢 fdcn 提示，更新之。这里确实是容易犯错。
猜想由于强类型判断导致性能不高（可在此测试），因此此种做法未见有性能的提升（还稍微慢了一些），而且还不能传递类似 [1,,,2,,] 这样的数组。所以还是淘宝UED上的解法比较科学（当然不是没有改进之处，比如不应该在 for 循环中声明变量）。
其实，这篇blog的意义在探讨如何避免无意义的消耗（比如计算 length）。但是鱼和熊掌不能兼得是自古之理，顾此失彼。当然，办法不是没有，比如数组的 forEach, map 方法等，可惜只有 gecko 浏览器才支持。
关于测试案例
数组是随机产生的1-100之间的整数，长度为5000，每个相同的大约重复5次。三个测试数组的元素构成是一致的。
总结
对数组的改变开销巨大，如果可能，尽量在不改变原有数组的情况下进行操作，如最终需要改变数组自身，可将结果赋予原有数组来操作。另外，对于 length 的计算，似乎效率并未受其影响。
啥时候我也该进补算法了，唉。软肋啊。
推荐阅读： 王元涛同学的 JavaScript 数组的 uniq 方法。
December 7th, 2007 at 22:32
请教一下，var ret = this.slice(); 的作用是什么，仅仅是返回调用uniq()方法的那个数组么？
December 8th, 2007 at 01:57
把[1,2,3,3,null, null,2]代入你的算法中試試
December 8th, 2007 at 04:30
我测试了,尽管你方法没有重复计算length,但是效率还比淘宝UED那个差一点点,单纯的length对效率的影响不是太大
December 8th, 2007 at 10:04
正如 fdcn 兄弟所言，确实有这样的问题，我也写了我的一个实现算法：
http://www.gracecode.com/Archive/Display/319
欢迎大家继续交流
December 8th, 2007 at 11:37
好像还是有问题，呵呵。
while (’undefined’ !== typeof this[i])
与
while(’undefined’ !== this[j])
不一样
是否应该为
while(undefined !== this[j])
即可？
December 8th, 2007 at 12:58
不好意思，再次更新。根据上述的问题，我重新优化了下算法，并将 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;
}
我写的相对几个函数的链接： http://www.gracecode.com/Archive/Display/319
December 10th, 2007 at 13:05
我在你的算法框架下改进成一个O(N)的算法，见http://www.pkblogs.com/todwang/2007/12/javascript-uniq.html
December 10th, 2007 at 17:49
如果数组里面元素类型是一样的话，换成下面这样会更快(时间缩短一半多)：
Array.prototype.uniq2 = function(){
var resultArr = [],
returnArr = [],
tempHash = {},
i = 1,
v,
origLen = this.length,
resultLen;
resultArr.push(this[0]);
for (i; i
December 10th, 2007 at 18:06
for (; i
December 22nd, 2007 at 19:13
理论上unique_slow那个会快……
个人认为是splice（）比较耗性能 所以实际会慢很多
December 25th, 2007 at 14:03
不用push会快一些
January 11th, 2008 at 01:39
测试了一下，你的新算法中function include函数单独做成Array.prototype.include，能更快一点。
January 12th, 2008 at 23:53
跟PrototypeJs的实现类似了。
如fdcn所说，include作为闭包函数，效率是不如拿出来做一个全局的函数。
January 18th, 2008 at 15:52
这两个函数写的真好～···
function include(arr, value){
for (var i=0, n=arr.length; i
January 18th, 2008 at 18:11
其实没有必要用新的数组，可以在原数组基础上修改：
Array.prototype.uniq2 = function () {
function seen( arr, ele, len ) {
for ( var i = 0; i
January 25th, 2008 at 17:20
我也写了下，貌似性能还不错。
http://www.zhaozhaozhu.com/bob/bob_array_uniq.html
另外，前两种方法的输出结果好象不太对吧。
January 28th, 2008 at 01:16
又学了一招。
February 21st, 2008 at 10:05
不懂算法,利用hash实现了一个
Array.prototype.uniq_freeman983 = function(){
window.status=’freeman983′;
var oa = this;
var ya = new Object();
var ra = [];
for(var i = 0; i
February 21st, 2008 at 11:03
不懂算法,利用hash实现了一个
http://freeman983.javaeye.com/blog/163799
April 8th, 2008 at 00:09
看了“博主”和“博客”的种种算法，很快，但是结果都不正确。
April 8th, 2008 at 20:21
题目我好像理解错了，但是：
1. 这个题目本身有歧义，条件也不明确（例如没有说明方法是否影响数组本身）；
2. 我认为返回“被删除元素”（所组成）的新数组没有什么意义；
3. 返回删除（重复）元素后的新数组不需要这些算法。
April 14th, 2008 at 16:18
freeman983的思路才叫巧妙…相形见绌阿~~赫赫