Guest User

Untitled

a guest
Jan 22nd, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. using namespace std;
  5.  
  6. void qSortVector(vector<int>&,int,int);
  7. int Partition(vector<int>&,int,int);
  8.  
  9. int main() {
  10.     vector<int> duplicates;
  11.     unordered_set<int> hashset;
  12.     int n;
  13.     cin>>n;
  14.     for (int k = 0; k<n; k++) {
  15.         int temp;
  16.         cin>> temp;
  17.         if (hashset.find(temp) == hashset.end()) {
  18.             hashset.insert(temp);
  19.         }
  20.         else{
  21.             duplicates.push_back(temp);
  22.            // cout<<"DUPLICATE : "<<temp<<endl;
  23.         }
  24.     }
  25.     qSortVector(duplicates,0,duplicates.size()-1);
  26. //    for(int i = 0; i<duplicates.size(); i++) {
  27. //        //cout<<duplicates[i]<<" KEK"<<endl;
  28. //    }
  29.     //bool checked = 0;
  30.     int lastNum = duplicates[0];
  31.     cout<<lastNum<<endl;
  32.     for(int i = 1; i < duplicates.size(); i++) {
  33.         if (duplicates[i] != lastNum){
  34.             cout<<duplicates[i]<<endl;
  35.             lastNum = duplicates[i];
  36.         }
  37.     }
  38.     return 0;
  39. }
  40.  
  41. void qSortVector(vector<int> &vec,int start,int end) {
  42.     if (start < end) {
  43.         int q = Partition(vec,start,end);
  44.         qSortVector(vec,start,q-1);
  45.         qSortVector(vec,q+1,end);
  46.     }
  47. }
  48.  
  49. int Partition(vector<int> &vec,int start,int end) {
  50.     int pivot = vec[end];
  51.     int i = start;
  52.     for(int j = start; j<end;j++) {
  53.         if (vec[j] <= pivot) {
  54.             swap(vec[i], vec[j]);
  55.             i++;
  56.         }
  57.     }
  58.     swap(vec[i], vec[end]);
  59.     return i;
  60. }
Add Comment
Please, Sign In to add comment