Solved

Remove duplicates from unsorted array

Posted on 2007-03-24
13
1,952 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
 
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
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
maze travler 6 47
c++ how to tell if the progra is ctl or mfc atl ect 6 54
Best book to learn C++ 4 55
Math Question 1 54
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

760 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

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now