How to remove duplicates from an array [duplicate]

Question

This question already has answers here:

Closed 14 years ago.

Possible Duplicate:
Array remove duplicate elements

This is a homework question. I think the best way is a modified merge sort, where the modified merge just does not copy duplicate elements from the two input arrays to the result array. The complexity is O(N*logN) (exactly as the regular merge sort). Does it make sense ? Are there any better solutions ?

• Cody Gray: Possible duplicates: stackoverflow.com/questions/3350641/…, stackoverflow.com/questions/9673/remove-duplicates-from-array, stackoverflow.com/questions/3432760/…, stackoverflow.com/questions/357421/…, stackoverflow.com/questions/4395668/…, stackoverflow.com/questions/1532819/…

Answer 1

If you do not need to sort, only remove the duplicates it can be done in O(N) time by using a HashSet (or your language equivalent).

• Michael: Thanks, I do not need them sorted. I can just copy the array elements into a set and copy the set into a array. BTW, one can use TreeSet to have the array sorted.
• threenplusone: Be careful. If you use TreeSet, you will revert back to O(n*log(N)).
• user166390: However, sorting allows n-way sorting or similar to be used, which is very handy if the data-set does not fit (well) into memory. But that's already into the realm of "other problems" :p
• Michael: @treenplusone Thanks, you are right about TreeSet.
• Ben Voigt: HashSet does a lookup in constant time for most datasets, but the bound is actually much worse.

Answer 2

Sounds good. Or you can do any kind of sort and then remove duplicates with complexity O(N)...

Answer 3

First you must Sorted the array Since it is a sorted array any duplicates would be next to each other. So start at the beginning and compare each element to it neighbor on its right. If there are no duplicates then you have made n-2 comparisons and you are done.

If you find a duplicate you are going to have a hole. Since it is an array an not a link list you will need to move every element down. (You could create a new array if that was allowed.) However you do not just want to start moving everything down, you can simply mark with a pointer or counter where the hole is and move on to the next comparison. When you get the next non-duplicate you move(copy) that element into the hole and increment your hole counter by 1.