Leetcode–Median of Two Sorted Arrays

The Problem:

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Notes:

  1. The median is the middle element in a sorted array if length is odd, the average of the two middle elements if length is even.
  2. Solution is required to be of O(log(m+n)), and two arrays are sorted, so here comes binary search. We convert  the problem of finding middle element to be finding the k-th element, and then the binary search is not always divide with the same length.
  3. In each recursion, discard part of A and B, with start and end index passed to next step, and update the k. If A[ida] < B[idb], means the part in A before ida are all of index less than k in merged array, and the part in B after idb are all of index greater than k in merged array, discard those two parts.
  4. Mistakes I made:
    1. when calculating the k related index in B, be careful of index-length conversion, should -1 here. Also should use the index count taken in A, not the index, so add astart to ida after B has calculated index.
    2. End condition need be thorough to include if either one has length zero.

Java Solution

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int lena = A.length;
        int lenb = B.length;
        
        if((lena + lenb)%2==0){// return (mid1+mid2)/2
            double mid1 = (double)getkth((lena+lenb)/2, A, 0, lena-1, B, 0, lenb-1);
            double mid2 = (double)getkth((lena+lenb)/2-1, A,0, lena-1, B, 0, lenb-1);
            return (mid1+mid2)/2;
        }
        else{
            return (double)getkth((lena+lenb)/2, A,0, lena-1, B, 0,lenb-1);
        }
    }
    
    private int getkth(int k, int A[], int astart, int aend, int B[], int bstart, int bend){
        
        int lena = aend-astart+1;
        int lenb = bend-bstart+1;

        if(lena==0)
            return B[bstart+k];
        if(lenb==0)
            return A[astart+k];
        if(k==0)
            return Math.min(A[astart], B[bstart]);
            
        int ida = k*lena/(lena+lenb);
        int idb = bstart + k-ida -1; //--!! important of -1, and here ida is used as count, not index
        ida = astart+ida; // --!! important to convert to index 
        
        if(A[ida] <= B[idb]){// discard the part after idb in B and part before ida in A
            k = k-(ida-astart+1);
            astart = ida+1;
            bend = idb;
        }
        else{// discard the part after ida in A and part before idb in B
            k = k-(idb-bstart+1);
            bstart =  idb+1;
            aend = ida;
        }
        return getkth(k, A, astart, aend, B, bstart, bend);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s