Advertisement
Kali_prasad

finding repeated numbers using merge sort

Mar 20th, 2022
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. void merge(vector<int> &v,int left,int right)
  5. {
  6.     int mid=(left+right)/2;
  7.    
  8.     int p1=left,p2=mid+1,k=0;
  9.     vector<int> temp(right-left+1);
  10.     while(p1<mid+1&&p2<right+1)
  11.     {
  12.         if(v[p1]<v[p2])
  13.         temp[k++]=v[p1++];
  14.         else
  15.         temp[k++]=v[p2++];
  16.     }
  17.     while(p1<mid+1)
  18.     temp[k++]=v[p1++];
  19.     while(p2<right+1)
  20.     temp[k++]=v[p2++];
  21.     k=0;
  22.     for(int i=left;i<=right;i++)
  23.     v[i]=temp[k++];
  24.    
  25.    
  26. }
  27. void MS(vector<int> &v,int left,int right)
  28. {
  29.     if(left==right)
  30.     return;
  31.    
  32.    
  33.     int mid=(left+right)/2;
  34.    
  35.     MS(v,left,mid);//left half sorting
  36.     MS(v,mid+1,right);//right half sorting
  37.     merge(v,left,right);//merging the two sorted parts
  38.     /* for(auto x:v)
  39.     cout<<x;
  40.     cout<<endl;*/
  41. }
  42. int main()
  43. {
  44.     int tc;
  45.     cin>>tc;
  46.     vector<int> c(tc);
  47.     vector<vector<int>> z;
  48.     for(int i=0;i<tc;i++)
  49.      {
  50.        
  51.          cin>>c[i];
  52.          vector<int> v(c[i]);
  53.          for(int j=0;j<c[i];j++)
  54.          {
  55.              int temp;
  56.              cin>>temp;
  57.              v[j]+=temp;
  58.          }
  59.          
  60.          MS(v,0,c[i]-1);
  61.         /* for(auto x:v)
  62.          {
  63.              cout<<x<<" ";
  64.          }cout<<endl;*/
  65.          z.push_back(v);
  66.      }
  67.  
  68.  
  69.    for(int i=0;i<tc;i++)
  70.     {
  71.         set<int> s;
  72.         vector<int> v=z[i];
  73.       for(int j=0;j<c[i];j++)
  74.       {
  75.           cout<<v[j]<<" ";
  76.          if(v[j]==v[j-1])
  77.          s.insert(v[j]);
  78.       }cout<<endl;
  79.      /* for(auto x:s)
  80.       cout<<x<<" ";
  81.       cout<<endl;*/
  82.     }
  83. }
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement