Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <vector>
- using namespace std;
- const int p = 999149;
- const int a = 1000;
- const int b = 2000;
- int hashFunction (int id, int n)
- {
- return ( ( ( a * id ) + b) % p ) % (n);
- }
- struct Node
- {
- int chiave;
- Node *left;
- Node *right;
- Node(int c): chiave(c), left(NULL), right(NULL){};
- };
- struct NodeDuplicati
- {
- int chiave;
- int duplcati;
- NodeDuplicati():chiave(-1), duplcati(0){};
- };
- class BinTree
- {
- Node * root_;
- NodeDuplicati x;
- vector<NodeDuplicati> v;
- void delTree(Node * &tree)
- {
- if(tree)
- {
- delTree(tree->left);
- delTree(tree->right);
- delete tree;
- tree = NULL;
- }
- }
- public:
- BinTree()
- {
- root_ = NULL;
- x.chiave = -1;
- x.duplcati = 0;
- }
- ~BinTree() {delTree(root_);};
- Node* getRoot(){return root_;};
- void insert(int i)
- {
- NodeDuplicati tmp;
- if(root_ == NULL)
- {
- tmp.chiave = i;
- tmp.duplcati = 1;
- v.push_back(tmp);
- insert_to_abr(i);
- x.chiave = i;
- x.duplcati = 1;
- }
- else
- {
- int trovato;
- trovato = search(i);
- if(trovato == -1)
- {
- tmp.chiave = i;
- tmp.duplcati = 1;
- v.push_back(tmp);
- insert_to_abr(i);
- if(x.duplcati == 1)
- {
- if(i > x.chiave)
- {
- x.chiave = i;
- x.duplcati = 1;
- }
- }
- }
- else
- {
- v[trovato].duplcati++;
- if(x.duplcati <= v[trovato].duplcati)
- {
- if(x.duplcati < v[trovato].duplcati)
- {
- x.chiave = v[trovato].chiave;
- x.duplcati = v[trovato].duplcati;
- }
- else
- {
- if(v[trovato].chiave > x.chiave)
- {
- x.chiave = v[trovato].chiave;
- x.duplcati = v[trovato].duplcati;
- }
- }
- }
- }
- }
- }
- int getChiave()
- {
- return x.chiave;
- }
- int getDuplicati()
- {
- return x.duplcati;
- }
- void insert_to_abr(int i)
- {
- Node *node = new Node(i);
- Node *pre = NULL;
- Node *post = root_;
- while(post != NULL)
- {
- pre = post;
- if(i <= post->chiave)
- post = post->left;
- else
- post = post->right;
- }
- if(pre == NULL)
- root_ = node;
- else if(i <= pre->chiave)
- pre->left = node;
- else
- pre->right = node;
- }
- int search(int i)
- {
- for (int j = 0; j < v.size(); j++)
- {
- if(v[j].chiave == i)
- return j;
- }
- return -1;
- }
- };
- bool compare(NodeDuplicati x, NodeDuplicati y)
- {
- if(x.chiave > y.chiave)
- return true;
- return false;
- }
- int main()
- {
- int N, K , S;
- cin >> N >> K >> S;
- vector<BinTree> hashtable(S);
- vector<NodeDuplicati> v(S);
- int chiave;
- int pos;
- for (int i = 0; i < N; i++)
- {
- cin >> chiave;
- pos = hashFunction(chiave, S);
- hashtable[pos].insert(chiave);
- }
- for (int i = 0; i < S; ++i)
- {
- v[i].chiave = hashtable[i].getChiave();
- v[i].duplcati = hashtable[i].getDuplicati();
- }
- sort(v.begin(), v.end(), compare);
- K = (K>S)?S:K;
- for (int i = 0; i < K; ++i)
- {
- if(v[i].duplcati != 0)
- cout << v[i].chiave << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement