fork download 
  1. #include <iostream>
  2. #include <set>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. using namespace std;
  6.  
  7. // Checking duplicates with Sorting, Complexity: O(nlog(n))
  8. bool checkDuplicatesWithSorting(int array[], int n)
  9. {
  10.  sort(array, array+n);
  11.  for(int i = 1; i < n; i++ )
  12.  {
  13.  	if(array[i]==array[i-1])
  14.  		return true;
  15.  }
  16.  return false;
  17. }
  18.  
  19. // Checking duplicates with a Set, Complexity: O(nlog(n))
  20. bool checkDuplicatesWithSet(int array[], int n)
  21. {
  22.  set <int> s(array, array+n);
  23.  return s.size() != n;
  24. }
  25.  
  26. // Checking duplicates with a Hashmap, Complexity: O(n) (Average Case)
  27. bool checkDuplicatesWithHashMap(int array[], int n)
  28. {
  29.  unordered_map<int, bool>uo_map;
  30.  for(int i=0;i<n;i++){
  31.  	if(uo_map.find(array[i]) ==  uo_map.end())
  32.  		uo_map[array[i]] = true;
  33.  	else return true;
  34.  }
  35.  return false;
  36. }
  37.  
  38. int main() {
  39. int arrayWithDuplicates[6] = {1,2,3,4,2,5};
  40. int arrayWithoutDuplicates[6] = {1,2,3,4,5,6};
  41. cout<<checkDuplicatesWithSorting(arrayWithDuplicates, 6)<<endl;
  42. cout<<checkDuplicatesWithSorting(arrayWithoutDuplicates, 6)<<endl;
  43. cout<<checkDuplicatesWithSet(arrayWithDuplicates, 6)<<endl;
  44. cout<<checkDuplicatesWithSet(arrayWithoutDuplicates, 6)<<endl;
  45. cout<<checkDuplicatesWithHashMap(arrayWithDuplicates, 6)<<endl;
  46. cout<<checkDuplicatesWithHashMap(arrayWithoutDuplicates, 6)<<endl;
  47. return 0;
  48. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin 
Standard input is empty
stdout 
1
0
1
0
1
0
https://ideone.com/Yja6oA
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!