Find the duplicate number from unsorted array

There are many methods to find out the duplicate numbers form the array. We can use the map which will store the values from the array as a key, while storing itself we can check for duplicate insertion. If map.insert flags out duplicate insertion that means we found out duplicate.
Code below uses the same technique to find the duplicate.

typefec vector<int> IntVect; void PrintDuplicateNumberFromUnsortedArrayWithMap(IntVect & A) {     std::map<int, int> mapOfInt;     std::pair<std::map<int, int>::iterator, bool> retVal;     for (int  i = 0; i < A.size(); i++)     {         retVal = mapOfInt.insert(make_pair(A[i], i));         if (retVal.second == false)         {             cout << "Found Duplicate for : " <<  A[i] << "  at : " << retVal.first->second  << endl;         }     } }

The above method is faster way to find the duplicate but it requires the storage.

If we want to avoid the temporary storage then we can just sort the array then find the duplicate by comparing the consecutive elements just in one pass as given in code below.

void FindDuplicateWithSorting(IntVect & vect) {     if (vect.size() > 0)     {         // Sort vector using any standard sort like quick sort         int prev = vect[0];         for (size_t i = 1; i < vect.size(); i++)         {             if (prev == vect[i])             {                 cout << "Duplicate exists for the number : " << prev << endl;             }             prev = vect[i];         }     } }

This code will have the time complexity equal to the time complexity of the sorting algorithm used for sorting the array because after sorting we will be using just one pass to search the duplicate.