Share my simple O(log(m+n)) solution for your reference


  • 159
    V

    Binary search. Call 2 times getkth and k is about half of (m + n). Every time call getkth can reduce the scale k to its half. So the time complexity is log(m + n).

    class Solution {
    public:
        int getkth(int s[], int m, int l[], int n, int k){
            // let m <= n
            if (m > n) 
                return getkth(l, n, s, m, k);
            if (m == 0)
                return l[k - 1];
            if (k == 1)
                return min(s[0], l[0]);
    
            int i = min(m, k / 2), j = min(n, k / 2);
            if (s[i - 1] > l[j - 1])
                return getkth(s, m, l + j, n - j, k - j);
            else
                return getkth(s + i, m - i, l, n, k - i);
            return 0;
        }
        
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            int l = (m + n + 1) >> 1;
            int r = (m + n + 2) >> 1;
            return (getkth(A, m ,B, n, l) + getkth(A, m, B, n, r)) / 2.0;
        }
    };

  • 7
    O

    could you explain int l = (m + n + 1) >> 1; int r = (m + n + 2) >> 1; ?


  • 1
    V

    get the medians. l and r are the medians.
    when n + m is even, l + 1 == r
    when n + m is odd, l == r
    we can merge 2 cases


  • 2
    J

    How can OJ accept it? for line return getkth(s, m, l + j, n - j, k - j);
    l is an array, while j is an integer, it can't compile.


  • 2
    S

    l + j means l[j]. Have you ever submitted this code? I did it. It is accepted.


  • 0
    V

    here l + j meas the address of l[j]


  • 0
    J

    I didn't submitted in OJ, but got compile error in local machine.


  • 0
    L

    Can you explain when "return 0" will be reached, or why we need "return 0" here? Plus, we may need cover the case when both arrays are empty


  • 0
    V

    it's my test code. I forget to delete it. Ignore this line.


  • 0
    D

    so when l == r, you will run it twice.


  • 1
    D

    it does not reduce the scale k to its half. in fact, k will be its 3/4 every time.


  • 0
    V

    u r right. For readable and my laziness, i don't add this opt.:-)


  • 0
    S

    This codes are great.

    if (m > n)
    return getkth(l, n, s, m, k);


  • 4
    Q

    I think j = min(n, k / 2) is not necessary. Because if k/2 > n then we must have k/2 > m also, since m <= n.

    Then in this case we cannot have the expected value since m+n < k. According to this algorithm it should not happen.

    And I change it to just j = k/2 the solution also accepted.


  • 0
    Y

    Yes, I agree with you!


  • 0
    W

    Hi vaputa,

    Thanks for your sharing! I might have further improved your solution to O(log(min(m,n)). Could you help to confirm the correctness of the complexity?

    class Solution {
    private:
        int getkth_(int nums1[], int len1, int nums2[], int len2, int k){ 
           if (len1 > len2) 
                return getkth_(nums2, len2, nums1, len1, k); 
           if(len1 == 0)
               return nums2[k-1];
           if(k==1)
               return min(nums1[0], nums2[0]);
           int i = (len1+1)/2, j = k - i;
           if(nums1[i-1] < nums2[j-1])
               return getkth_(nums1+i, len1-i, nums2, j, k-i);
           else
               return getkth_(nums1, i, nums2+j, len2-j, k-j);
        }
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len1 = nums1.size(), len2 = nums2.size();
            int k = (len1 + len2 + 1) >> 1;
            if((len1 + len2) & 1)
                return getkth_(&nums1[0], len1 ,&nums2[0], len2, k); 
            else {
                return (getkth_(&nums1[0], len1 ,&nums2[0], len2, k) + getkth_(&nums1[0], len1 ,&nums2[0], len2, k+1)) / 2.0;
            }   
        }
    };

  • 0
    L

    I have got the same idea too.

    however, there is a large chance that this code is wrong.

       if(nums1[i-1] < nums2[j-1])
           return getkth_(nums1+i, len1-i, nums2, j, k-i);
       else
           return getkth_(nums1, i, nums2+j, len2-j, k-j);
    

    what if nums1[i-1]==nums2[j-1] ?
    it seems when this happen, you can do nothing with a step of K(but it's ok with a step of k/2).

    haven't figured out yet....


  • 0
    W

    I think your concern doesn't exist. The condition of "nums1[i-1]==nums2[j-1]" can be merged into both ">" and "<". I merged it into ">" in above snippet. Because we can guarantee that if they are equal, at least one of them is not the median we want.


  • 0
    Q

    This is what I think can be rather easier to implement in real time, with findKth, if you know findKth

    Awesome


  • 3
    P

    I think :
    return (getkth(A, m ,B, n, l) + getkth(A, m, B, n, r)) / 2.0;
    can make better to
    if(l == r) return getKth(A, size1 ,B, size2, l);
    return (getkth(A, size1 ,B, size2, l) + getkth(A, size1, B, size2, r)) / 2.0;

    So when (m+n) is odd, it only calls getkth() once.


Log in to reply
 

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