1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
|
#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
using std::cout;
using std::cin;
using std::endl;
using std::unordered_set;
using std::vector;
template<class TimeUnit = std::chrono::milliseconds>
class Timer {
public:
Timer()
{
m_start = std::chrono::steady_clock::now();
}
~Timer()
{
std::chrono::steady_clock::time_point stop = std::chrono::steady_clock::now();
std::cout << "** Running time: " << std::chrono::duration_cast<TimeUnit>(stop - m_start).count();
}
private:
std::chrono::steady_clock::time_point m_start;
};
// Print duplicates in arr[0..n-1] using unordered_set
void printDuplicates(int arr[], int n)
{
// declaring unordered sets for checking and storing
// duplicates
unordered_set<int> intSet;
unordered_set<int> duplicate;
// looping through array elements
for (int i = 0; i < n; i++) {
// if element is not there then insert that
if (intSet.find(arr[i]) == intSet.end())
intSet.insert(arr[i]);
// if element is already there then insert into
// duplicate set
else
duplicate.insert(arr[i]);
}
// printing the result
//cout << "Duplicate items are : ";
unordered_set<int> ::iterator itr;
// iterator itr loops from begin() till end()
for (itr = duplicate.begin(); itr != duplicate.end(); itr++)
cout << *itr << " ";
}
// Print duplicates in arr[0..n-1] using std::map
// based on some code from SO
void print_duplicates(int arr[], int n)
{
std::map<int, size_t> cntMap;
for (int i = 0; i < n; ++i)
cntMap[arr[i]]++;
for (const auto&[first,second] : cntMap)
//cout << first << "-> " << second << "\n";
if (second > 1)
cout << first << " ";
}
int main()
{
int arr[] = { 1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5 };
int n = sizeof(arr) / sizeof(int);
{
Timer<std::chrono::microseconds> t;
printDuplicates(arr, n);
}
cout << " micros \n";
{
Timer<std::chrono::microseconds> t;
print_duplicates(arr, n);
}
cout << " micros \n";
}
|