Saturday, July 30, 2005

how can i find all duplicate values within an array?

FAQTs - Knowledge Base - View Entry - how can i find all duplicate values within an array?

how can i find all duplicate values within an array?
Sep 10th, 2004 13:29

Gavin Kistner, Jean-Bernard Valentaten, Periklis a





Well, there is more than one way to achieve this.
The easiest one is to walk the array position by position with two
loops:

for (var i=0; i{
for (var j=i+1; j {
if (myArray[i] == myArray[j])
myArray[j] = '';
}
}

This will do the job, but is very inefficient (especially with large
arrays), since a lot of comparisons are made. One might start to
optimize this code, but believe me, a slow algorithm will always stay
slow, no matter how much you optimize it.
The better way is to sort the array and then have a loop walk it once:

myArray.sort();

for (var i=0; i{
if (myArray[i] == myArray[i+1])
myArray[i+1] = '';
}

Note that the above solution does not account for objects stored in
the array which may be technically different (== computes to false)
but trivially the same. For example:

var myArray = [
{ name:'Gavin', age:31 },
{ name:'Lisa', age:30 },
{ name:'Gavin', age:23 },
{ name:'Gavin', age:31 }
];

In the above, technically
myArray[0] != myArray[3]
even though you know it is. For something like this you can write your
own comparison function:

Array.prototype.removeDuplicates = function( customCompare ){
if ( customCompare ){
this.sort(customCompare);
for (var i=0; i<(this.length-1); i++)
{
if ( !customCompare(this[i],this[i+1]) ){
this.splice( (i--)+1, 1 );
}
}
}else{
this.sort();
for (var i=0; i<(this.length-1); i++)
{
if (this[i]==this[i+1]){
this.splice( (i--)+1, 1 );
}
}
}
return this;
}


You would call the above passing in the same sort of custom comparison
function as the myArray.sort() method takes:

myArray.removeDuplicates( function(a,b){
return a.nameb.name ? 1 :
a.age b.age ? 1 : 0;
} );
Post a Comment