• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 298
  • Last Modified:

Duplicate Element

How to remove duplicate elements in C?

int main()
{

   int a[] = { 10,20,30,40,50,10,20,50};  // how to remove duplicates from this array
 
  return (0);
}


0
gauravflame
Asked:
gauravflame
2 Solutions
 
ozoCommented:
Are all the elements small integers?
Would you me satisfied with an O(n*n) method?
0
 
gauravflameAuthor Commented:
can you provide me both solution in O(n*n) and in O(nlogn)
0
 
ozoCommented:
O(n*n) for each item, scan the array to see if the item has been seen before
O(n*log(n)) sort the array (but do you want to preserver order?)
O(n) or O(max item) time O(max item) space:  keep an array indexed by item to record seen items
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
gauravflameAuthor Commented:
O(n) solution will be great.
How to implement in this form?
0
 
gauravflameAuthor Commented:
I know how to do in O(n*n) times .. .. still this is not a best way to do
still I have problem in this way , what I shat I do when I will get duplicate element
int a[] = { 10,20,30,40,50,10,20,50};  
for(int i =0; i < 5; i++)
{
   for(int j =0; j < 5; j++)
   {
            if(a[i] == a[j])
                {  
                        printf("Dupicate Found");
                        // How to remove the element from the array  ..so that array don't contain
                        // empty element
               }
  }
}



0
 
Infinity08Commented:
>> // How to remove the element from the array

If increased storage is no concern, then you might consider a linked list instead of an array. The problem with removing an element from an array is that you have to shift all elements after that. A linked list doesn't have that problem.

You could also, instead of removing the element from the array, just set it to an invalid value (eg. -1), and ignore it in the further operations of the array. Depending of the application, and how many elements you are gonna remove, that might be a valid alternative.


0
 
ozoCommented:
int n=0;
for(int i =0; i < 5; i++)
{
  int j=0;
  for( j =0; j < i; j++)
    {
      if(a[i] == a[j])
        {
          printf("Dupicate Found");
          // How to remove the element from the array  ..so that array don't contain
          // empty element
          break;
        }
    }
  if( j==i ){
    a[n++]=a[i];
  }
}

///the first n elements of the array are now unique
0
 
gauravflameAuthor Commented:
The above solution is O(n*n) times  .Can you provide me the solution in the O(n) time

0
 
ozoCommented:
// this is O(n + max element)
// with a little more work, it could be made O(n), assuming O(max element) fits in memory
// if it does not fit, you could still do it in O(n) expected time, O(n log n) worst case

#include <stdlib.h>
#define len(a) (sizeof(a)/sizeof(*a))
int n=0;
unsigned int m=0;
 for(int i=0; i < len(a); i++){ if( a[i] > m ){ m = a[i]; } }
 char *s=(char *)calloc(m,1);
 for(int i =0; i < len(a); i++){
  int j=0;
  if( !s[a[i]] ){
    a[n++]=a[i];
  }
  s[a[i]]=1;
}
0
 
abithCommented:
O(n) times :)

this will run only if array contains less than 70

      int repeat[]= {10,10,50,20,20,30,40,50,10,20,50};
      int start = 0;
      int pos =0;
      char flag = 0;
      int i ;
      for (i=0; i < sizeof(repeat)/ sizeof(*repeat); i++)
      {
            int c = repeat[i] / 10 ;
            if(!( flag & (1 << (c+1)) ))
            {
                  repeat[start++] = repeat[pos];
                  flag |= (1 << (c+1));
            }            
            pos++;
      }      

      for (i=0;i<start;i++)
            cout << repeat[i] << endl;
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now