Efficient duplicates search algorithm

Question

I need a script to search efficiently all the duplicates in a one-dimensional array. I tried a naive method :

for(var i=0, ii<arr.length-1; i<ii; i++)
    for(var j=i+1, jj<arr.length; j<jj; j++)
        if(arr[i] == arr[j])
            // remove the duplicate

Very simple but it takes a too long time if the array contains a large set of values. The tables that I use often contain hundreds of thousands of values, so that the number of iterations required for this operation is HUGE !

If someone has an idea !?

unless you have some restrictions on the values I would vote for the dup. — Karoly Horvath
– Karoly Horvath, Commented Feb 14, 2014 at 10:57

Niklas B. · Accepted Answer · 2014-02-14 17:12:31Z

2

Use a LinkedHashSet or OrderedHashSet implementation, it does not allow duplicates and provides expected O(1) on insertion, lookup, and deletion. Since your OP says you want to remove the duplicates, there is no faster way to do this than O(n). In an array of 1,000,000 items max time was 16ms

Create a LinkedHashSet hs
foreach object obj in arr -- hs.add(obj);

Complexity is expected O(n) with a good hash function.

edited Feb 14, 2014 at 17:12

Niklas B.

95.8k18 gold badges201 silver badges228 bronze badges

answered Feb 14, 2014 at 11:51

TheJackal

4354 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

AlexD Over a year ago

Strictly speaking, hash set does not guarantee O(n) complexity.

TheJackal Over a year ago

I never said that it does, I said that removing duplicates from the dataset is worst case O(n). HashSet guarantees O(1) for operations

AlexD Over a year ago

I meant that using of hash set does not guarantee overall O(n) complexity. No, hash set does not guarantee O(1) due to possible hash collisions.

guy777 Over a year ago

Ok, i try up this solution. A verification before add a value into array seems a good solution for me !

TheJackal Over a year ago

My mistake, LinkedHashSet or OrderHashSet implementation avoids collisions. Could you explain why it does not guarantee O(n)? If the number of objects in the array are known, capacity can be set.

|

MissingNumber · Accepted Answer · 2014-02-14 12:04:39Z

0

This code could be the most efficient way you can do it ..!! Which is nothing but the direct implementation of set .

function eliminateDuplicates(arr) {
  var i,
      len=arr.length,
      out=[],
      obj={};

  for (i=0;i<len;i++) {
    obj[arr[i]]=0;
  }
  for (i in obj) {
    out.push(i);
  }
  return out;
}

edited Feb 14, 2014 at 12:04

answered Feb 14, 2014 at 11:57

MissingNumber

1,18215 silver badges29 bronze badges

Collectives™ on Stack Overflow

Efficient duplicates search algorithm

2 Answers 2

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related