利用javascript编写一个去除数组重复项的方法，时间复杂度O(n),大家看看有没有什么漏洞或者写出自己更好的方法
<html>
?<head>
??<script type="text/javascript">
???function distinct(arr){
????var rs = new Array();
????for(var i=0;i<arr.length;i++){
?????var s = ","+rs.join(",")+",";
?????if(!s.match(","+arr[i]+",")){
??????rs.push(arr[i]);
?????}?
????}
????return rs;
???}
???var r = new Array(1,2,212,2);
???alert(distinct(r).toString());
??</script>
?</head>
?<body>
?</body>
</html>
1 楼
hyj1254
2010-12-03
我也来一个：
var array=[1,1,2,2,3,3];
var newArry=[];
for(var x in array){
newArry[array[x]]="";
}
for(var y in newArry){
alert(y);
}
2 楼
clue
2010-12-03
楼主的程序只能处理不含","的字符串，并且用正则匹配效率会比较低吧？
时间复杂度也不应该算O(n)，因为随着rs的增长，要匹配搜索的字符串也在增长。
楼上的程序也只能处理字符串，并且破坏了顺序
另外for in循环比较危险，它会枚举原型链上的属性
如果数组中只有字符串的话，还是比较容易处理的：
时间复杂度也不应该算O(n)，因为随着rs的增长，要匹配搜索的字符串也在增长。
楼上的程序也只能处理字符串，并且破坏了顺序
另外for in循环比较危险，它会枚举原型链上的属性
如果数组中只有字符串的话，还是比较容易处理的：
var s = ["a","b","a","c"];
var arr = [], map = {}, n, i;
for(i=0; i<s.length; i++){
n = s[i];
if(!map.hasOwnProperty(n)){
map[n] = true;
arr.push(n);
}
}
console.log(arr);
3 楼
hehoha_wj
2010-12-03
人多力量大啊，谢谢兄弟们，可以提供这么多解决方法。三楼的方法好，关键我以前不知道hasOwnProperty这个东西，学习了。
4 楼
hyj1254
2010-12-03
引用
楼上的程序也只能处理字符串，并且破坏了顺序
另外for in循环比较危险，它会枚举原型链上的属性
另外for in循环比较危险，它会枚举原型链上的属性
按楼上所述试验了一把:
Array.prototype.say="haha";
var array=[new Object(),"1,2#<%^&*()+}[]{",2,2,3,3,4,4,6,6,5,5];
var newArry=[];
for(var x in array){
newArry[array[x]]="";
}
for(var y in newArry){
alert(y+" "+typeof y);
}
结论：
这种写法也能处理除字符串外的其他数据。。
也没有破坏顺序。
但最后一条确实是那样的，会枚举原型链属性，需要使用hasOwnProperty。
5 楼
cai3178940
2010-12-03
来个简单点的
var array=["a","b","c","a"];
for(var i=0;i<array.length;i++){
for(var j=i+1;j<array.length;j++){
if(array[j]==array[i]) array.splice(j,1)
}
}
alert(array);
6 楼
cai3178940
2010-12-03
稍微改改，适合任何类型去重
var array=[2.3,2.3,"a","b","b",true,true,false,1,0,undefined,null];
for(var i=0;i<array.length;i++){
for(var j=i+1;j<array.length;j++){
if(array[j]===array[i]) array.splice(j,1)
}
}
alert(array);
7 楼
hyj1254
2010-12-03
楼上的方法不错，但最好修改下，呵呵：
var array=[2.3,2.3,"a","b","b",true,true,true,false,1,0,undefined,null];
for(var i=0;i<array.length;i++){
for(var j=i+1;j<array.length;j++){
if(array[j]===array[i]) {
array.splice(j,1);
j--;
}
}
}
alert(array);
8 楼
cai3178940
2010-12-03
hyj1254 写道
楼上的方法不错，但最好修改下，呵呵：
var array=[2.3,2.3,"a","b","b",true,true,true,false,1,0,undefined,null];
for(var i=0;i<array.length;i++){
for(var j=i+1;j<array.length;j++){
if(array[j]===array[i]) {
array.splice(j,1);
j--;
}
}
}
alert(array);
嗯，的确是这么回事，之前没注意，谢谢楼上
9 楼
clue
2010-12-03
引用
楼上的程序也只能处理字符串，并且破坏了顺序
另外for in循环比较危险，它会枚举原型链上的属性
另外for in循环比较危险，它会枚举原型链上的属性
按楼上所述试验了一把:
Array.prototype.say="haha";
var array=[new Object(),"1,2#
----------------------------
回复出了问题，被截断了，见后面重发的回帖
10 楼
clue
2010-12-03
hyj1254 写道
结论：
这种写法也能处理除字符串外的其他数据。。
也没有破坏顺序。
但最后一条确实是那样的，会枚举原型链属性，需要使用hasOwnProperty。
试试这个就知道了： [{a:1}, {b:1}, "[object Object]"]
11 楼
hyj1254
2010-12-03
[{a:1}, {b:1}, "[object Object]"]这个确实是，都成[object Object]了。
12 楼
smzd
2010-12-03
好像一些方法的调用都是不用时间的，所以不会被记录在O(n)中，比如说Array.splice……
13 楼
Jwind
2010-12-05
hyj1254 写道
我也来一个：
var array=[1,1,2,2,3,3];
var newArry=[];
for(var x in array){
newArry[array[x]]="";
}
for(var y in newArry){
alert(y);
}
这种方法，我也用过，但是在for(var y in newArry)这样遍历的时候，多出了indeOf和另外一个（忘记是什么了），不知道是什么原因，当时没太去管，谁能解释一下？
14 楼
hyj1254
2010-12-06
引用
但是在for(var y in newArry)这样遍历的时候，多出了indeOf和另外一个
这个应该是把prototype中的属性或方法给读出来了。参考下前面的讨论。
15 楼
dagmom
2010-12-06
cai3178940 写道
hyj1254 写道
楼上的方法不错，但最好修改下，呵呵：
var array=[2.3,2.3,"a","b","b",true,true,true,false,1,0,undefined,null];
for(var i=0;i<array.length;i++){
for(var j=i+1;j<array.length;j++){
if(array[j]===array[i]) {
array.splice(j,1);
j--;
}
}
}
alert(array);
嗯，的确是这么回事，之前没注意，谢谢楼上
false后面的项全部丢失，求解？
16 楼
hyj1254
2010-12-06
var array=[false,undefined,null]; alert(array);
引用
false后面的项全部丢失
17 楼
dagmom
2010-12-06
hyj1254 写道
var array=[false,undefined,null]; alert(array);
引用
false后面的项全部丢失
不好意思，我上的一段代码里面看错了，把===写成了==，呵呵！
18 楼
goolcona
2010-12-07
(function($) {
$.extend($, {
arrunique : function(array) {
var ret = [], done = {};
try {
for (var i = 0, length = array.length; i < length; i++) {
var tmp = array[i];
if (!done[tmp]) {
done[tmp] = true;
ret.push(tmp);
}
}
} catch (e) {
ret = array;
}
return ret;
}
});
})(jQuery);
jQuery本身有一个工具方法 jQuery.unique(array)，但是在1.3的时候对于纯粹的数组去重有些问题，上面的代码改了源码一点。
$.extend($, {
arrunique : function(array) {
var ret = [], done = {};
try {
for (var i = 0, length = array.length; i < length; i++) {
var tmp = array[i];
if (!done[tmp]) {
done[tmp] = true;
ret.push(tmp);
}
}
} catch (e) {
ret = array;
}
return ret;
}
});
})(jQuery);
jQuery本身有一个工具方法 jQuery.unique(array)，但是在1.3的时候对于纯粹的数组去重有些问题，上面的代码改了源码一点。
19 楼
superobin
2010-12-10
正常的大家都写了。。我乱写个递归的。。嘿嘿，原理是一样的
var ary = [1,1,1,1,1,1,2,32,,1,1,1,1,1,213,14,3,25,,,,51512,,"fasfasfsa",null,NaN,1,function(){},function(){},function(){},{},{},[],"fasfasfsa"];
(function(index) {
index = index||0;
for(var i=index+1;i<ary.length;i++) {
if(ary[i] === ary[index]) {
ary = ary.slice(0,i).concat(ary.slice(i--+1));
}
}
if(ary.length-index>1) {
arguments.callee(index+1);
}
})();