C++ O(m+n) solution


  • 0
    C

    class Solution {
    public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {

     int *C = new int[m+n];
     
     merge(A,m,B,n,C,m+n);
     
     int pos=(m+n)/2; double d;
     if((m+n)%2==0)
     {
         d=(C[pos-1]+C[pos])/2.0;
     }
     else
      d=C[(m+n)/2];
     delete []C;
        return d;
    }
    
    void merge(int A[], int m, int B[], int n, int C[],int t)
    {
        int i=0,j=0,k=0;
        
        while(i<m && j<n)
        {
            if(A[i]<=B[j])
            {
                C[k]=A[i];
                i++;
                k++;
            }
            else
            {
                C[k]=B[j];
                j++;
                k++;
            }
        }
        
        if(i<m)
        {
            for(int p=i;p<m;p++)
            {
                C[k]=A[p];k++;
            }
        }
        if(j<n)
        {
            for(int p=j;p<n;p++)
            {
                C[k]=B[p];
                k++;
            }
        }
    }
    

    };


Log in to reply
 

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