DaniWeb Forum Index > Software Development > C++

Find the duplicate numbers in a set of ints

Please support our C++ advertiser: Intel Parallel Studio Home

Last »

•

Join Date: Jun 2007

Posts: 16

Reputation: kinggarden is an unknown quantity at this point

Solved Threads: 0

kinggarden kinggarden is offline

Offline

Newbie Poster

Find the duplicate numbers in a set of ints

Jun 19th, 2007

Hi, everybody.

The question is :

if the user input a set of numbers, you don't know how long the

set is, like 1, 2, 3, 4, 5, 5, 5, 6, 1, 3, -1, -12141, 123, -1...., you are

asked to find the dumplicate numbers in this set. I mean 1, 5, -1.

Acturally, I just can find an o(n ^ 2) algorithm by scaning the

set for n times.

I think there must be a better way, maybe O(n) or less

Just for fun

Last edited by kinggarden; Jun 19th, 2007 at 6:31 am.

Rock Mu

I will keep walking!

Shanghai, China

•

Join Date: Jun 2007

Posts: 16

Reputation: kinggarden is an unknown quantity at this point

Solved Threads: 0

kinggarden kinggarden is offline

Offline

Newbie Poster

Re: Find the dumplicate numbers in a set of ints

Jun 19th, 2007

Sorry, dumplicate -> duplicate

I don't know how to edit the title

Rock Mu

I will keep walking!

Shanghai, China

•

Join Date: Feb 2007

Posts: 539

Reputation: thekashyap will become famous soon enough

Solved Threads: 50

thekashyap thekashyap is offline

Offline

Posting Pro

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

sorting the list should help.

Are you Agile.. ?

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

if you are not alowed to reorder the original sequence, but are allowed to use auxiliary storage

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <vector>
#include <set>
#include <iostream>
#include <string>
using namespace std;
 
template< typename CNTR >
void print_duplicates( const CNTR& cntr )
{
  set< typename CNTR::value_type > unique ;
  for( size_t i=0 ; i<cntr.size() ; ++i )
    if( !unique.insert( cntr[i] ).second )
      cout << "duplicate " << cntr[i] << '\n' ;
}
 
int main()
{
  string str ; cin >> str ;
  vector<int> v( str.begin(), str.end() ) ;
  print_duplicates(v) ;
}
#include <vector>
#include <set>
#include <iostream>
#include <string>
using namespace std;

template< typename CNTR >
void print_duplicates( const CNTR& cntr )
{
  set< typename CNTR::value_type > unique ;
  for( size_t i=0 ; i<cntr.size() ; ++i )
    if( !unique.insert( cntr[i] ).second )
      cout << "duplicate " << cntr[i] << '\n' ;
}

int main()
{
  string str ; cin >> str ;
  vector<int> v( str.begin(), str.end() ) ;
  print_duplicates(v) ;
}

this would take O( N log N ). instead of a set, if you use a hashtable with a good hash function, you could do this in linear time.

•

Join Date: Sep 2004

Posts: 7,802

Reputation: Narue has a reputation beyond repute

Solved Threads: 747

Narue

Offline

Code Goddess

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

>sorting the list should help.
Sorting the list with a general algorithm gives you (at best) O(NlogN) performance just for the sort. Then you have to determine the duplicates. It also means that you have to store the list somewhere first, which means your storage cost is O(N). If there are a lot of duplicates, you're wasting storage for this problem. See below.

>this would take O( N log N ).
That's a curious solution. Why didn't you go with a map instead?

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <cstdlib>
#include <iostream>
#include <map>
 
int main()
{
  std::map<int, int> freq;
 
  for ( int i = 0; i < 30; i++ )
    ++freq[std::rand() % 20];
 
  std::cout<<"Duplicates:\n";
  std::map<int, int>::iterator it = freq.begin();
 
  while ( it != freq.end() ) {
    if ( it->second > 1 )
      std::cout<< it->first <<" -- "<< it->second <<" times\n";
 
    ++it;
  }
}
#include <cstdlib>
#include <iostream>
#include <map>

int main()
{
  std::map<int, int> freq;

  for ( int i = 0; i < 30; i++ )
    ++freq[std::rand() % 20];

  std::cout<<"Duplicates:\n";
  std::map<int, int>::iterator it = freq.begin();

  while ( it != freq.end() ) {
    if ( it->second > 1 )
      std::cout<< it->first <<" -- "<< it->second <<" times\n";

    ++it;
  }
}

Not only does this give you a unique list, it also marks each of the duplicates for later use. That's a great deal more flexible than what you have, which can only mark duplicates once.

Of course, it still has a storage problem because of the counter for each item. Even if you use the map as your primary data structure rather than the vector you're using now, it's still effectively a 2N storage cost for integers. Since the OP only seems to want the duplicates, you can remove all but the duplicates with fair ease and limit the storage penalty to when nearly every number has at least one duplicate:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <cstdlib>
#include <iostream>
#include <map>
 
void mark_sweep ( std::map<int, int>& mark )
{
  std::map<int, int>::iterator it = mark.begin();
  std::map<int, int> sweep;
 
  while ( it != mark.end() ) {
    if ( it->second > 1 )
      sweep.insert ( *it );
    ++it;
  }
 
  mark.swap ( sweep );
}
 
int main()
{
  std::map<int, int> freq;
 
  for ( int i = 0; i < 30; i++ )
    ++freq[std::rand() % 20];
  mark_sweep ( freq );
 
  std::cout<<"Duplicates:\n";
  std::map<int, int>::iterator it = freq.begin();
 
  while ( it != freq.end() ) {
    std::cout<< it->first <<" -- "<< it->second <<" times\n";
    ++it;
  }
}
#include <cstdlib>
#include <iostream>
#include <map>

void mark_sweep ( std::map<int, int>& mark )
{
  std::map<int, int>::iterator it = mark.begin();
  std::map<int, int> sweep;

  while ( it != mark.end() ) {
    if ( it->second > 1 )
      sweep.insert ( *it );
    ++it;
  }

  mark.swap ( sweep );
}

int main()
{
  std::map<int, int> freq;

  for ( int i = 0; i < 30; i++ )
    ++freq[std::rand() % 20];
  mark_sweep ( freq );

  std::cout<<"Duplicates:\n";
  std::map<int, int>::iterator it = freq.begin();

  while ( it != freq.end() ) {
    std::cout<< it->first <<" -- "<< it->second <<" times\n";
    ++it;
  }
}

Last edited by Narue; Jun 19th, 2007 at 3:04 pm.

I'm here to prove you wrong.

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

•

Originally Posted by vijayan121

if you are not alowed to reorder the original sequence, but are allowed to use auxiliary storage
Help with Code Tags

C++ Syntax (Toggle Plain Text)
#include <vector>
#include <set>
#include <iostream>
#include <string>
using namespace std;
 
template< typename CNTR >
void print_duplicates( const CNTR& cntr )
{
  set< typename CNTR::value_type > unique ;
  for( size_t i=0 ; i<cntr.size() ; ++i )
    if( !unique.insert( cntr[i] ).second )
      cout << "duplicate " << cntr[i] << '\n' ;
}
 
int main()
{
  string str ; cin >> str ;
  vector<int> v( str.begin(), str.end() ) ;
  print_duplicates(v) ;
}
#include <vector> #include <set> #include <iostream> #include <string> using namespace std; template< typename CNTR > void print_duplicates( const CNTR& cntr ) { set< typename CNTR::value_type > unique ; for( size_t i=0 ; i<cntr.size() ; ++i ) if( !unique.insert( cntr[i] ).second ) cout << "duplicate " << cntr[i] << '\n' ; } int main() { string str ; cin >> str ; vector<int> v( str.begin(), str.end() ) ; print_duplicates(v) ; }
this would take O( N log N ). instead of a set, if you use a hashtable with a good hash function, you could do this in linear time.

What input are you using, I don't get anything intelligible for the output?

*Voted best profile in the world*

•

Join Date: Sep 2004

Posts: 7,802

Reputation: Narue has a reputation beyond repute

Solved Threads: 747

Narue

Offline

Code Goddess

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

>What input are you using, I don't get anything intelligible for the output?
It's kind of goofy. He uses the characters in a string to initialize the vector of integers. You have to input a string with no spaces, and the output will be the integer code for each of the characters in the string. Try "012345123" as input. Assuming ASCII, you'll get 49, 50, and 51 as the duplicates.

I'm here to prove you wrong.

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

•

Originally Posted by Narue

>What input are you using, I don't get anything intelligible for the output?
It's kind of goofy. He uses the characters in a string to initialize the vector of integers. You have to input a string with no spaces, and the output will be the integer code for each of the characters in the string. Try "012345123" as input. Assuming ASCII, you'll get 49, 50, and 51 as the duplicates.

Ah...

*Voted best profile in the world*

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Find the duplicate numbers in a set of ints

Jun 19th, 2007

> why didn't you go with a map instead
because i was working under the premise:
if you are not alowed to reorder the original sequence, but are allowed to use auxiliary storage

> ...it also marks each of the duplicates for later use. That's a great deal
> more flexible than what you have ...
true.

here is an extract from the python cookbook (this is to remove, not just identify duplicates) [Raymond Hettinger, 2002]

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
def uniq(alist)    # Fastest order preserving
  set = {}
  return [set.setdefault(e,e) for e in alist if e not in set]
 
def uniq(alist)    # Fastest without order preserving
  set = {}
  map(set.__setitem__, alist, [])
  return set.keys()
def uniq(alist)    # Fastest order preserving
  set = {}
  return [set.setdefault(e,e) for e in alist if e not in set]

def uniq(alist)    # Fastest without order preserving
  set = {}
  map(set.__setitem__, alist, [])
  return set.keys()