>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?
#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:
#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;
}
}
Offline 
Unsolved 
