Can someone write C program to remove duplicate entries from an array with less than O(n2) complexity ?

Question

Input: {5, 8, 5, 3, 3, 2, 7}
Output: {5, 8, 3, 2, 7, ?, ?}

Idea is that we should remove the duplicate number from the array and should return the array in the original form (obviously without duplicate).

Please help me with an efficient algorithm or C code.

Answer 1

If we make a binary search tree of this array elements then duplicate elements can be removed in less than O(n2) complexity

Answer 2

o(nLogn)

void removeDups(int array[],int len)
{
  int   b,d,i,j;

  if(len<1)
    return;

  for(b=len-1,d=len-2;d>=0;d--)
  {
    if(array[d]!=array)
    {
      b--;
      array=array[d];
    }
  }

  for(i=b,j=0;j<len;i++,j++)
  {
    if(i<len)
      array[j]=array;
    else
      array[j]=-1;
  }
}

Comments

It can be done in O(n) complexity by using Hash Function.

---

but hash requires a lot of memory if we want to avoid collision and size is very large.

---

It is correct that collision problem will be there in case of large size array. But in that case we can create a function like removeDuplicate() for a fixed size array and we can break our large array into small pieces and can send it to the function for removal of duplicates. At last we can combine these small pieces into original one. But for this we will have use temp memory. So do not forget to free all temp memory after the whole process.