22ms C code with explanation


  • -6
    C
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int C[m+n];//result array
        int im=0;
        int in=0;
        //This while loop combines the 2 arrays, the result array remains sorted.If m!=n, this while is not enough
        while(im<m && in < n){
            if(A[im]<=B[in]){
                im++;
                C[im+in-1] = A[im-1];
            }else{  
                in++;
                C[im+in-1] = B[in-1];
            }
        }
        //The following if completes the job left by the above while. Puts the last elements in the longer array into the result array 
        if(im<m){
            for(im;im<m;im++){
                C[im+in] = A[im];
            }
        }else if(in < n){
            for(in;in<n;in++){
                C[im+in] = B[in];
            }
        }
        //return according to the size of the result array
        if((m+n)%2==0)
            return ((float)C[(m+n)/2] + C[(m+n-1)/2])/2;
        else
        	return C[(m+n)/2];
    }

  • 2
    L

    Isn't its time complexity O(m+n)?


  • 0
    N

    This is really a good solution for this question , but i thought the time should be 0( m + n).


Log in to reply
 

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