Share my o(log(min(m,n)) solution


  • 0
    X

    class Solution {
    public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int *sa = m <= n ? A : B;
    int *la = m <= n ? B : A;
    const int lens = m <= n ? m: n;
    const int lenl = m <= n ? n: m;

        const int c = (lens + lenl -1) / 2;
    
        int ls = 0;
        int us = lens - 1;
    
        const bool odd = (m + n) % 2;
        double result = 0;
        if (!lens && lenl)
                result = odd ? la[c] : la[c] + la[c+1];
    
        while (ls <= us)
        {
                const int cs = (us + ls) / 2;
                const int cl = c - cs;
    
                if (sa[cs] < la[cl])
                {
                        if (ls != cs)
                                ls = cs;
                        else if (cl == 0 || sa[cs] >= la[cl-1])
                        {
                                result = sa[cs];
                                if (!odd) result += cs < (lens-1) ? min(sa[cs+1], la[cl]) : la[cl];
                                break;
                        }
                        else if (cs == us)
                        {
                                result = la[cl-1];
                                if (!odd) result += la[cl];
                                break;
                        }
                        else
                                ls = cs + 1;
                }
                else if (sa[cs] > la[cl])
                {
                        if (us != cs)
                                us = cs;
                        else if (cs == ls || la[cl] >= sa[cs-1])
                        {
                                result = la[cl];
                                if (!odd) result += cl < (lenl-1) ? min(sa[cs], la[cl+1]) : sa[cs];
                                break;
                        }
                        else
                                us = cs - 1;
                }
                else
                {
                        result = sa[cs];
                        if (!odd) result += la[cl];
                        break;
                }
        }
    
        return odd ? result : result / 2;
    }
    

    };


Log in to reply
 

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