top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+4 votes
622 views
Can someone write C program to remove duplicate entries from an array with less than O(n2) complexity ?
posted Sep 18, 2013 by Ganesh Kumar

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+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 by Vikram Singh
+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
+5 votes

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.

+3 votes

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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...