My solution which doesn't include recursion. Easy to be understood.


  • -2
    X
    class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) 
        {
            if(m == 0)
            {
                return (B[(n-1)/2] + B[n/2])/2.0;
            }
            if(n == 0)
            {
                return (A[(m-1)/2] + A[m/2])/2.0;
            }
            int *pA = A, *pB = B;
            int i = 0, ia = 0, ib = 0;
            int temp = 0;
            while(1)
            {
                if((*pA <= *pB && ia < m) || (ib >= n)) 
                {
                    pA++;
                    i++;
                    ia++;
                    if(i == (m + n + 1)/2)
                    {
                        if((m + n) % 2)
                        {
                            return *(pA-1);
                        }
                        else
                        {
                            temp = *(pA-1);
                        }
                    }
                    else if(i == (m + n + 2)/2)
                    {
                        return (*(pA-1) + temp)/2.0;
                    }
                }
                else
                {
                    pB++;
                    i++;
                    ib++;
                    if(i == (m + n + 1)/2)
                    {
                        if((m + n) % 2)
                        {
                            return *(pB-1);
                        }
                        else
                        {
                            temp = *(pB-1);
                        }
                    }
                    else if(i == (m + n + 2)/2)
                    {
                        return (*(pB-1) + temp) / 2.0;
                    }
                }
            }
        }
    };

  • 0
    S

    The time complexity is O(n+m) not O(log(n+m))!


Log in to reply
 

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