Solved

Remove duplicates from unsorted array

Posted on 2007-03-24
13
1,977 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
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 
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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

860 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