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

632 views
Can someone write C program to remove duplicate entries from an array with less than O(n2) complexity ? posted Sep 18, 2013

+1 vote

If we make a binary search tree of this array elements then duplicate elements can be removed in less than O(n2) complexity answer Sep 18, 2013
+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;
}
}
`````` answer Sep 18, 2013 by anonymous
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.
Similar Questions

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).

Given a 2d array, u need to sort the 2 diagonals independently.
And the elements in diagonal should remain in diagonal only.

INPUT =>
24 2 3 4 7

6 13 8 5 10

11 12 9 14 15

16 21 18 25 20

17 22 23 24 1

OUTPUT =>
1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25