Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Remove duplicates from unsorted array

Posted on 2007-03-24
13
Medium Priority
?
2,137 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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:Deepu Abraham
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:Deepu Abraham
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 2000 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

Independent Software Vendors: 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!

Question has a verified solution.

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

The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

604 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