很经典的问题,去除数组中的重复元素,上网搜了一下,发现大多数无论转载还是原创都是这个解法:
错误解法:
function uniq(array) { var map={}; var re=[]; for(var i=0,l=array.length;i<l;i++) { if(typeof map[array[i]] == "undefined"){ map[array[i]]=1; re.push(array[i]); } } return re; }
如果用过java等高级语言的话,初看这段代码确实没有什么问题:下面的例子:
uniq([1,2,1,2,4]);
也能正常运行。
可再试试下面的例子:
uniq([{x:1},"[object Object]"]); uniq([{x:1},{z:2}]);
运行一下就会知道错在哪里了!
HashMap In Java :
在 java 中如 HashMap 类可以使用对象做为 key (内部实现使用 hashcode散列到桶 以及桶内equals[默认内存地址]比较),如:
class Holder { int i; } public class Test3 { /** * @param args */ public static void main(String[] args) { HashMap<Holder, Holder> map=new HashMap<Holder, Holder>(); Holder key= new Holder(); Holder value= new Holder(); value.i=1; map.put(key, value); Holder key2=new Holder(); System.out.println(map.get(key).i); System.out.println(map.get(key2)); } }
Object In Javascript:
而在 javascript 中毕竟没有map,只有对象这个概念,而对象则要求其属性值必须为字符串,如果提供给对象的属性不是字符串,那么则会自动调用 toString 方法转化为字符串形式,例如:
var x={}; var y={ toString:function(){ return "z"; } }; x[y]=1; alert(x["z"]);
那么由上述例子就可以知道第一个程序为什么是错误的了 。
正确答案:
我们无法利用高级语言提供的map类库,那就只好两遍遍历数组了,也是 taobao ued提供的标准答案:
注意 === 使用。
/** *unique the array *@param {Array} array array to unique *@return {Array} uniqued array ,note change parameter */ function undulpicate(array){ for(var i=0;i<array.length;i++) { for(var j=i+1;j<array.length;j++) { //注意 === if(array[i]===array[j]) { array.splice(j,1); j--; } } } return array; }
ps: Jquery Uniq Node
如果我们确认数组里每个元素都是对象,那么可以用加标签的方式,给对象元素添加标签,从而把时间复杂度提升到 O(n) :
var x={z:1}; var y={q:2}; function uniqObjects(array){ var re=[]; for(var i=0,l=array.length;i<l;i++) { if(typeof array[i]["_uniqObjects"] == "undefined"){ //添加标签 array[i]["_uniqObjects"]=1; re.push(array[i]); } } //取出标签 for(var i=0,l=re.length;i<l;i++) { delete re[i]["_uniqObjects"]; } return re; } uniqObjects([x,y,x]);
这也正是 jquery 的思路,由于每个元素都是节点数组,当然可以这样做了:
unique: function( array ) { var ret = [], done = {}; try { for ( var i = 0, length = array.length; i < length; i++ ) { var id = jQuery.data( array[ i ] ); if ( !done[ id ] ) { done[ id ] = true; ret.push( array[ i ] ); } } } catch( e ) { ret = array; } return ret; },
注意:对基本类型,如 number,string,不要使用这种方式,它们会产生临时对象,并不能达到预期效果!