fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <cstddef>
  6. // I wrote this off the top of my head with no consideration, ignore the quirks.
  7.  
  8. /// Helper Functions ////
  9. /////////////////////////
  10. int compare(const void * a, const void * b){if((int)a <  (int)b)return -1; if((int)a == (int)b)return 0; return 1;}
  11.  
  12. class hashtable { //There is probably something wrong with this, but it works enough to demonstrate the logic.
  13.     private:
  14.         int * table, * table_accessed; //0 = no access, 1 =access, n+1 = n key collisions
  15.         std::size_t length;
  16.  
  17.         int hashy(int element){
  18.             std::size_t hash = (element) % this->length;
  19.             if(*(this->table+hash) != element)
  20.                 hashy(element * ++(*(this->table_accessed+hash))); 
  21.             return hash;
  22.         }     
  23.     public:
  24.         hashtable(std::size_t _length) 
  25.             : table(new int[_length]), 
  26.               table_accessed(new int[_length]()), 
  27.               length(_length)
  28.             {}
  29.         ~hashtable(){delete [] table; delete [] table_accessed;}
  30.  
  31.         bool insert(int element){
  32.             std::size_t index = hashy(element);
  33.  
  34.             if((*(this->table+index) == element) && (*(this->table_accessed+index) == 1)){  
  35.                 return true;
  36.             } else if(*(this->table_accessed+index) > 1) {
  37.                 if(*(this->table + hashy(element * (*(this->table_accessed+index)))) == element)
  38.                     return true;
  39.             }
  40.  
  41.             *(this->table+index) = element;
  42.             (*(this->table_accessed+index))++;
  43.  
  44.             return false;
  45.         }
  46. }; 
  47.  
  48. //// Array Element is Different Algorithms ////
  49. ///////////////////////////////////////////////
  50. //naive, O(n^2)?
  51. const bool ArrElemDif_naive(const int * array_start, std::size_t array_length){
  52.     for(std::size_t current = 0; current < array_length; current++){
  53.         for(std::size_t offset = current+1; offset < array_length; offset++){
  54.             if(*(array_start+current) == *(array_start+offset)){
  55.                 return false;
  56.             }
  57.         }
  58.     }
  59.  
  60.     return true;
  61. }
  62.  
  63. //extra computation time necessary for sort, O(n * (n log n))? 
  64. const bool ArrElemDif_sort(int * array_start, std::size_t array_length){
  65.     int * tmp_array = new int[array_length];
  66.     for(std::size_t i = 0; i < array_length; *(tmp_array+i) = *(array_start+i), i++);
  67.  
  68.     qsort(tmp_array, array_length, sizeof(int), compare);
  69.     for(std::size_t index = 0; (index+1) != array_length; index++){
  70.         if(*(tmp_array+index) == *(tmp_array+index+1)){
  71.             return false;
  72.         }
  73.     }
  74.  
  75.     delete [] tmp_array;
  76.     return true;
  77. }
  78.  
  79. //higher memory usage, O(n)?
  80. const bool ArrElemDif_table(const int * array_start, std::size_t array_length){
  81.     class hashtable a(array_length);
  82.     for(std::size_t i = 0; i < array_length; i++){
  83.        if(a.insert(*(array_start+i))){
  84.            return false;
  85.        }
  86.     }
  87.  
  88.     return true;
  89. }
  90.  
  91. /////TESTER FUNCTION/////
  92. /////////////////////////
  93. void test(int * array_start, std::size_t array_length, bool isunique){
  94.     for(std::size_t i = 0; i < array_length; i++, *(array_start+i) = (isunique ?  i : rand() % (i+1)))
  95.         printf("%d ",*(array_start+i));
  96.  
  97.     std::cout << std::endl << "naive: " << std::boolalpha << ArrElemDif_naive(array_start, array_length) << std::endl;
  98.     std::cout << "sort : " << std::boolalpha << ArrElemDif_sort(array_start, array_length) << std::endl;
  99.     std::cout << "table: " << std::boolalpha << ArrElemDif_table(array_start, array_length) << std::endl << std::endl;
  100. }
  101. /////////////////////////
  102.  
  103.  
  104. #define LIST_SIZE 50
  105. int main(void){
  106.     srand(time(NULL));
  107.  
  108.     int * list = new int[LIST_SIZE];
  109.  
  110.     test(list, LIST_SIZE, false);
  111.     test(list, LIST_SIZE, true);
  112.  
  113.     delete [] list;
  114.     return 0;
  115. }
Success #stdin #stdout 0s 2988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 1 0 3 2 5 6 2 9 11 6 5 3 3 8 16 6 10 2 13 21 4 6 16 3 15 19 8 26 2 29 6 32 5 8 26 5 23 21 16 15 30 44 24 36 19 30 27 
naive: false
sort : false
table: false

0 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 
naive: true
sort : true
table: true
https://ideone.com/GKzjL4
language:
C++ (gcc 8.3)
created:
10 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!