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

+4 votes

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

+1 vote

+1 vote

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;
}
}
```

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

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.

...