1

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 ?

Community
  • 1
  • 1
Michael
  • 41,026
  • 70
  • 193
  • 341
  • 1
    Possible duplicates: http://stackoverflow.com/questions/3350641/array-remove-duplicate-elements, http://stackoverflow.com/questions/9673/remove-duplicates-from-array, http://stackoverflow.com/questions/3432760/remove-duplicate-elements-in-an-array-in-on-in-c-c, http://stackoverflow.com/questions/357421/what-is-the-best-way-to-remove-duplicates-in-an-array-in-java, http://stackoverflow.com/questions/4395668/remove-duplicates-from-array-without-using-hash-table, http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array – Cody Gray - on strike Jan 02 '11 at 06:18

3 Answers3

4

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).

threenplusone
  • 2,112
  • 19
  • 28
  • 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. – Michael Jan 02 '11 at 06:38
  • 1
    Be careful. If you use TreeSet, you will revert back to O(n*log(N)). – threenplusone Jan 02 '11 at 06:43
  • 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 –  Jan 02 '11 at 07:00
  • @treenplusone Thanks, you are right about TreeSet. – Michael Jan 02 '11 at 07:32
  • HashSet does a lookup in constant time for most datasets, but the bound is actually much worse. – Ben Voigt Jan 02 '11 at 21:17
1

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

Ilya Kogan
  • 21,995
  • 15
  • 85
  • 141
0

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.

user527619
  • 89
  • 1
  • 1
  • 6