Median of running stream in O(nlog(n)) time complexity? A++


  • 1
    N
    #include<iostream>
    
    using namespace std;
    int sizM=0, sizN=0 ;
    int M[500], N[500];
    
    void  MaxHeapify(int i)
     {
    if(i>=sizM) return;
         int curr=i;
         int l=i*2+1;
         int r=i*2+2;
    
         if(l<sizM && M[curr]<M[l])
              curr=l;
         if(r<sizM && M[curr]<M[r])
                curr=r;
    
         if(curr!=i)
         {   swap(M[curr],M[i]);
             MaxHeapify(curr);
        }
     }
    void  MinHeapify(int i)
     {
    
          if(i>=sizN) return;
         int curr=i;//3542
         int l=i*2+1;
         int r=i*2+2;
    
         if(l<sizN && N[curr]>N[l])
              curr=l;
         if(r<sizN && N[curr]>N[r])
                curr=r;
    
         if(curr!=i)
         {   swap(N[curr],N[i]);
             MinHeapify(curr);
        }
     }
    
    void  MaxHeapifyBU(int i)
     {
    
    
         int parent=(i-1)/2;
         int t=parent;
         int l=parent*2+1;
         int r=parent*2+2;
    
         if(l<sizM && M[parent]<M[l])
              parent=l;
         if(r<sizM && M[parent]<M[r])
                parent=r;
    
         if(parent!=(i-1)/2)
         {   swap(M[parent],M[t]);
             MaxHeapifyBU(t);
        }
    
     }
    
    void  MinHeapifyBU(int i)
     {
    
    
         int parent=(i-1)/2;
         int t=parent;
         int l=parent*2+1;
         int r=parent*2+2;
    
         if(l<sizN && N[parent]>N[l])
              parent=l;
         if(r<sizN && N[parent]>N[r])
                parent=r;
    
         if(t!=parent)
         {
             swap(N[parent],N[t]);
             MinHeapifyBU(t);
        }
     }
    void  Maxinsert(int key)
     {
    
         sizM++;
         M[sizM-1]=key;
    
         MaxHeapifyBU(sizM-1);
     }
     void Mininsert(int key)
     {
    
         sizN++;
         N[sizN-1]=key;
    
         MinHeapifyBU(sizN-1);
     }
    
    int  NeedHelp(int key)
     {
    
    
         if(sizM==0)
          {
              Maxinsert(key);
              return M[0];
          }
         if(sizN==0)
          {
              Mininsert(key);
              return (M[0]+N[0])/2;
          }
         if(key<M[0])
         {
             swap(M[0],key);        //key should be in middle of M[0] and N[0]...
             MaxHeapify(0);
         }
         else
         if(key>N[0])
         {
             swap(N[0],key);        //key should be in middle of M[0] and N[0]...
             MinHeapify(0);
         }
    
         if(sizM>sizN)
             Mininsert(key);
          else
              Maxinsert(key);
    
        if(sizM==sizN)
             return (M[0]+N[0])/2;
          else
            return sizM>sizN?M[0]:N[0];         //@IIT BHU @omp3010 
     }
    
    int main()
    {
    
       int a[]={5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4};
    
        int n=sizeof(a)/sizeof(a[0]);
    
        for(int i=0 ;i<n ;i++)
            cout<<NeedHelp(a[i])<<endl;
    
        return 0;
    }

  • 0
    N
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.