Entry

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<myArray.length - 1; i++)
{
  for (var j=i+1; j<myArray.length; 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<myArray.length - 1; 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.name<b.name ? -1 : a.name>b.name ? 1 :
      a.age<b.age ? -1 : a.age > b.age ? 1 : 0;
   } );