Removing duplicate pointers from an array of pointers to any generic type

Question

Is there a generic way to remove duplicate pointers from an array, e.g for an input like this:

return this:

without requiring any knowledge of the types of the things that the pointers are pointing at?

Answer 1

I would do the following:

• sort the array of pointers — O(n lg n)
• go through the array, copying out first occurrences to another array — O(n)

Keeping track of whether a pointer is a duplicate is extremely easy if the array is sorted: you just save the last one copied and don't copy the next one across until it's different.

Another simple brute-force approach (if you need to preserve the order of the pointers in the original array) would be to search forward in the array replacing duplicates with NULL. This has O(n^2) complexity, but you may not care for modest array sizes. For example:

k=0
for(i=0; i<n; i++) {
   if( myarray[i] == NULL ) {
       continue;
   }
   current = myarray[i];
   unique[k] = current;
   k++;
   for(j=i+1; j<n; j++) {
       if( current == myarray[j] ) {
           myarray[j] = NULL;
       }
   }
}

Answer 2

Using a hash table helps, here is a solution with expected case O(N) [not worst case].

H = Empty Hash Table

foreach ptr in Array:
    if ptr NOT present in H:
        insert ptr to H

// H now have every ptr only once

wi = 1                    // write index
for ri = 1..n:            // read index
    ptr = Array[ ri ]
    if ptr in H:
        Array[ wi ] = ptr
        remove ptr from H
        wi++