Advertisement
Guest User

Untitled

a guest
Sep 16th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6.  
  7.  
  8. const int p = 999149;
  9. const int a = 1000;
  10. const int b = 2000;
  11.  
  12. int hashFunction (int id, int n)
  13. {
  14.     return ( ( ( a * id ) + b) % p ) % (n);
  15. }
  16.  
  17. struct Node
  18. {
  19.     int chiave;
  20.     Node *left;
  21.     Node *right;
  22.     Node(int c): chiave(c), left(NULL), right(NULL){};
  23. };
  24. struct NodeDuplicati
  25. {
  26.     int chiave;
  27.     int duplcati;
  28.     NodeDuplicati():chiave(-1), duplcati(0){};
  29. };
  30. class BinTree
  31. {
  32.     Node * root_;
  33.     NodeDuplicati x;
  34.     vector<NodeDuplicati> v;
  35.  
  36.     void delTree(Node * &tree)
  37.     {
  38.         if(tree)
  39.         {
  40.             delTree(tree->left);
  41.             delTree(tree->right);
  42.             delete tree;
  43.             tree = NULL;
  44.         }
  45.     }
  46. public:
  47.     BinTree()
  48.     {
  49.         root_ = NULL;
  50.         x.chiave = -1;
  51.         x.duplcati = 0;
  52.     }
  53.     ~BinTree() {delTree(root_);};
  54.     Node* getRoot(){return root_;};
  55.  
  56.     void insert(int i)
  57.     {
  58.         NodeDuplicati tmp;
  59.         if(root_ == NULL)
  60.         {
  61.             tmp.chiave = i;
  62.             tmp.duplcati = 1;
  63.             v.push_back(tmp);
  64.             insert_to_abr(i);
  65.             x.chiave = i;
  66.             x.duplcati = 1;
  67.         }
  68.         else
  69.         {
  70.             int trovato;
  71.             trovato = search(i);
  72.             if(trovato == -1)
  73.             {
  74.                 tmp.chiave = i;
  75.                 tmp.duplcati = 1;
  76.                 v.push_back(tmp);
  77.                 insert_to_abr(i);
  78.                 if(x.duplcati == 1)
  79.                 {
  80.                     if(i > x.chiave)
  81.                     {
  82.                         x.chiave = i;
  83.                         x.duplcati = 1;
  84.                     }
  85.                 }
  86.             }
  87.             else
  88.             {
  89.                 v[trovato].duplcati++;
  90.                 if(x.duplcati <= v[trovato].duplcati)
  91.                 {
  92.                     if(x.duplcati < v[trovato].duplcati)
  93.                     {
  94.                         x.chiave = v[trovato].chiave;
  95.                         x.duplcati = v[trovato].duplcati;
  96.                     }
  97.                     else
  98.                     {
  99.                         if(v[trovato].chiave > x.chiave)
  100.                         {
  101.                             x.chiave = v[trovato].chiave;
  102.                             x.duplcati = v[trovato].duplcati;
  103.                         }
  104.                     }
  105.  
  106.                 }
  107.             }
  108.         }
  109.     }
  110.     int getChiave()
  111.     {
  112.         return x.chiave;
  113.     }
  114.     int getDuplicati()
  115.     {
  116.         return x.duplcati;
  117.     }
  118.     void insert_to_abr(int i)
  119.     {
  120.         Node *node = new Node(i);
  121.         Node *pre = NULL;
  122.         Node *post = root_;
  123.         while(post != NULL)
  124.         {
  125.             pre = post;
  126.             if(i <= post->chiave)
  127.                 post = post->left;
  128.             else
  129.                 post = post->right;
  130.         }
  131.         if(pre == NULL)
  132.             root_ = node;
  133.         else if(i <= pre->chiave)
  134.             pre->left = node;
  135.         else
  136.             pre->right = node;
  137.     }
  138.     int search(int i)
  139.     {
  140.         for (int j = 0; j < v.size(); j++)
  141.         {
  142.             if(v[j].chiave ==  i)
  143.                 return j;
  144.         }
  145.         return -1;
  146.     }
  147. };
  148.  
  149. bool compare(NodeDuplicati x, NodeDuplicati y)
  150. {
  151.     if(x.chiave > y.chiave)
  152.         return true;
  153.  
  154.     return false;
  155. }
  156.  
  157. int main()
  158. {
  159.     int N, K , S;
  160.     cin >> N >> K >> S;
  161.     vector<BinTree> hashtable(S);
  162.     vector<NodeDuplicati> v(S);
  163.     int chiave;
  164.     int pos;
  165.  
  166.     for (int i = 0; i < N; i++)
  167.     {
  168.         cin >> chiave;
  169.         pos = hashFunction(chiave, S);
  170.         hashtable[pos].insert(chiave);
  171.     }
  172.     for (int i = 0; i < S; ++i)
  173.     {
  174.         v[i].chiave = hashtable[i].getChiave();
  175.         v[i].duplcati = hashtable[i].getDuplicati();
  176.     }
  177.     sort(v.begin(), v.end(), compare);
  178.     K = (K>S)?S:K;
  179.     for (int i = 0; i < K; ++i)
  180.     {
  181.         if(v[i].duplcati != 0)
  182.             cout << v[i].chiave << endl;
  183.     }
  184. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement