How to remove duplicates from an array

Question

Possible duplicate:
Array remove duplicate items

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

Answer 1

If you do not need to sort, delete only duplicates, this can be done O (N) times using a HashSet (or the equivalent of your language).

Answer 2

That sounds good. Or you can do any kind and then remove duplicates with O (N) complexity ...

Answer 3

You must sort the array first. Since this is a sorted array, any duplicates will be next to each other. So, start from the beginning and compare each element with its neighbor on the right. If there are no duplicates, you made n-2 comparisons, and you're done.

If you find a duplicate, you will have a hole. Since this is an array, not a list of links, you will need to move each element down. (You can create a new array if it was allowed.) However, you do not just want to start moving everything, 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) this element into the hole and increase the hole counter by 1.