Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2283
  • Last Modified:

Remove duplicates from unsorted array

I need an 0(N*N) solution (algorithm or pseudo code) without sorting the array. The array should also be compressed.

Thanks
0
gromul
Asked:
gromul
  • 3
  • 2
  • 2
  • +5
1 Solution
 
ozoCommented:
perl -ne 'print unless $seen{$_}++' < array > unique
0
 
ozoCommented:
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
 
gromulAuthor Commented:
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's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
ozoCommented:
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
 
Deepu AbrahamR & D Engineering ManagerCommented:
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
 
Deepu AbrahamR & D Engineering ManagerCommented:
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
 
jkrCommented:
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
 
MacroLandCommented:
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
 
MacroLandCommented:
BTW, I now realized that mine seems very similar to ozo's 3rd post.

Regards,
0
 
DarrylshCommented:
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
 
jkrCommented:
>>The easiest thing is to just copy the elements to a <set>

That requires additional/temp. storage, which 'unique()' doesn't.
0
 
itsmeandnobodyelseCommented:
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
 
HurbCommented:
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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 3
  • 2
  • 2
  • +5
Tackle projects and never again get stuck behind a technical roadblock.
Join Now