Solved

Remove duplicates from unsorted array

Posted on 2007-03-24
13
1,968 Views
Last Modified: 2008-01-09
I need an 0(N*N) solution (algorithm or pseudo code) without sorting the array. The array should also be compressed.

Thanks
0
Comment
Question by:gromul
  • 3
  • 2
  • 2
  • +5
13 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 18787024
perl -ne 'print unless $seen{$_}++' < array > unique
0
 
LVL 84

Expert Comment

by:ozo
ID: 18787030
If you want O(N*N) you could do a linear search for each element to see if you already have it.
What kind of compression do you want to do?
0
 

Author Comment

by:gromul
ID: 18787282
Would you mind providing some C++ pseudo code or algorithm? As for the compression, I was thinking of this: array 1 2 25 2 3 4 would become 1 2 25 3 4 (second 2 was removed).
0
Use Case: Protecting a Hybrid Cloud Infrastructure

Microsoft Azure is rapidly becoming the norm in dynamic IT environments. This document describes the challenges that organizations face when protecting data in a hybrid cloud IT environment and presents a use case to demonstrate how Acronis Backup protects all data.

 
LVL 84

Expert Comment

by:ozo
ID: 18787432
set put poiinter = get pointer = first element in array
while get pointer in array
  scan array from beginning to put pointer
  if the scanned element is the same as the element to get skip this duplicate
  else if we complete the scan without finding the new element
    copy from the get pointer to the put pointer and and advance the put pointer
advance the get pointer

put pointer now points to the end of a list of unique elements


0
 
LVL 11

Expert Comment

by:DeepuAbrahamK
ID: 18787764
Removing elements from the sorted list is always easy and efficient. Do you want to keep the index of the elements as it is?
You could use stl::map
http://www.cprogramming.com/tutorial/stl/stlmap.html
Best Regards,
DeepuAbrahamK
0
 
LVL 11

Expert Comment

by:DeepuAbrahamK
ID: 18787937
Try inserting every items into the map and while inserting items into map put a check whether the item is available already in the map.That way you will avoid duplicates.

Here is a sample:

    map<int,int> mymap;
    map<int,int>::iterator iter;
    int item[]={1, 2, 25, 2, 3, 4};

    // Here are example strings that I will add to an empty map
    int N = 6;

    for(int i=0;i<N;i++)
    {
   
     if(mymap.find(item[i]) != mymap.end())
     mymap[i] = item[i];

    }
   
    // Here is the output of the map in order from beginning to end

    cout << "This is the output of the map in order" << endl;

    for(iter = mymap.begin(); iter != mymap.end(); iter++)
    {
        cout << (*iter).first << " => " << iter->second << endl;    
    }

Best Regards,
DeepuAbrahamK
0
 
LVL 86

Expert Comment

by:jkr
ID: 18788375
Consider using STL's 'unique()': http://www.sgi.com/tech/stl/unique.html

Example
Remove duplicates from consecutive groups of equal ints.

vector<int> V;
V.push_back(1);
V.push_back(3);
V.push_back(3);
V.push_back(3);
V.push_back(2);
V.push_back(2);
V.push_back(1);

vector<int>::iterator new_end = unique(V.begin(), V.end());
copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
    // The output it "1 3 2 1".
0
 
LVL 4

Expert Comment

by:MacroLand
ID: 18788618
a list data type is very efficient for deleting and inserting elements anywhere within the list which takes O(1) time. This is O(n) for vectors.

To remove duplicates you can initiliaze two list iterators.
1) curr=front of the list
2) p=next to current

p searches the list for the value of curr and if found removes it. As it goes end of the list then curr goes to next position and p is again next to curr. The algorithm continues this way and it takes O(n^2) time.

Regards,
0
 
LVL 4

Expert Comment

by:MacroLand
ID: 18788628
BTW, I now realized that mine seems very similar to ozo's 3rd post.

Regards,
0
 
LVL 3

Expert Comment

by:Darrylsh
ID: 18790380
The easiest thing is to just copy the elements to a <set> .  Only unique value will copy and requires no further checking.  A <map> technically would work since it only inserts unique keys as well but why bother inserting <pairs> when you don't need to.

0
 
LVL 86

Expert Comment

by:jkr
ID: 18790440
>>The easiest thing is to just copy the elements to a <set>

That requires additional/temp. storage, which 'unique()' doesn't.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 500 total points
ID: 18793232
Maybe that:

for (int i = 0; i < size-1; ++i)
    for (int j = i+1; j < size; ++j)
           if (array[i] == array[j])
           {
                  int n = (--size-j) * sizeof(array[0]);
                  if (n > 0)
                      memmove(&array[j], &array[j+1], n);
                  j--;  // index j must be checked again
            }

Regards, Alex

0
 
LVL 2

Expert Comment

by:Hurb
ID: 18803729
maybe an o(N) sol, not very effiecient on memory though. If you have enough memory or know the limits on the number you could:

int items[]={1,2,25,2,3,4};
int newitems[100],ind=0;
int inarray[10000];

for(i=0;i<10000;i++)inarray[i]=0;

for(i=0;i<n;i++)if(!inarray[items[i]])
{
  newitems[ind++]=items[i];
  inarray[items[i]]=1;
}
0

Featured Post

ScreenConnect 6.0 Free Trial

Discover new time-saving features in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI, app configurations and chat acknowledgement to improve customer engagement!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

832 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question