algorithm - Remove duplicates from Array without using Hash Table

Question

i have an array which might contain duplicate elements(more than two duplicates of an element). I wonder if it's possible to find and remove the duplicates in the array:

• without using Hash Table (strict requirement)
• without using a temporary secondary array. No restrictions on complexity.

P.S: This is not Home work question

Was asked to my friend in yahoo technical interview

Answer 1

Sort the source array. Find consecutive elements that are equal. (I.e. what std::unique does in C++ land). Total complexity is N lg N, or merely N if the input is already sorted.

To remove duplicates, you can copy elements from later in the array over elements earlier in the array also in linear time. Simply keep a pointer to the new logical end of the container, and copy the next distinct element to that new logical end at each step. (Again, exactly like std::unique does (In fact, why not just download an implementation of std::unique and do exactly what it does? :P))