数组去重问题

xiaoxiao2021-03-01  8

很经典的问题,去除数组中的重复元素,上网搜了一下,发现大多数无论转载还是原创都是这个解法:

错误解法:

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,不要使用这种方式,它们会产生临时对象,并不能达到预期效果!

 

 

转载请注明原文地址: https://www.6miu.com/read-3100010.html

最新回复(0)