Thursday, January 1, 2015

4. Median of Two Sorted Arrays Leet code Java

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)).

Solution:
Define k=(m+n+1)/2;
If m+n is an odd number, this problem is equal to find the kth number, if it is an even number then find the average of kth number and (k+1)th number.
The solution is pick the (m)th number(a[m]) from Array that has shorter length, and compare it to the (k-m-1)th(b[k-m-1]) number and(k-m-2)th(b[k-m-2]) number in the other array,if a[m] is in the range of[b[k-m-2],b[k-m-1]) then a[m] is the kth number, if(a[m]>b[k-m-1]) it means the kth number is in the first half of the array(A[l]->A[m]),else then it is in the range of(A[m]->A[r]).
After the iteration if we couldn't find the element in the shorter array, the kth element should be in the longer array, and all the elements in the shorter array before l pointer will be smaller than kth number. So the kth number will be b[k-l-1].
We need to pay attention to some corner case when we try to find the (k+1) element. 
The running time is the O(log(min(m,n))).



 public double findMedianSortedArrays(int A[], int B[]) {  
    if(A==null) return findMedianHelper(A,B);  
    if(B==null) return findMedianHelper(B,A);  
    if(A.length<B.length) return findMedianHelper(A,B);  
    else return findMedianHelper(B,A);  
   }    
   public double findMedianHelper(int A[],int B[]){    
    int la=(A==null)? 0: A.length;  
    int lb=(A==null)? 0: B.length;  
    if (lb==0) return 0;  
    int k=(la+lb+1)/2;  
    int res1=0;  
    int res2=0;  
    int l=0;  
    int r=la-1;  
    while(l<=r){  
      int m=(r-l)/2+l;  
      if(k-m-1==0){ // only can occur when la==lb  
       res1=Math.min(A[m],B[0]);  
       res2=(lb==1)? Math.max(A[m],B[0]):Math.min(B[1],Math.max(A[m],B[0]));  
       return ((la+lb)%2==0)? ((double)res1+(double)res2)/2 : (double)res1;  
      }  
      else{  
        if(A[m]<=B[k-m-1] && A[m]>=B[k-m-2]){  
          res1=A[m];  
          res2=(m==A.length-1)? B[k-m-1] : Math.min(A[m+1],B[k-m-1]);  
          return ((la+lb)%2==0)? ((double)res1+(double)res2)/2 : (double)res1;  
        }  
        else if(A[m]>B[k-m-1]) r=m-1;  
        else l=m+1;  
      }  
    }  
    res1=B[k-l-1];  
    if(l==la) res2=(k-l==lb)? B[k-l-1]:B[k-l];  
    else res2=(k-l==lb)? A[l]: Math.min(A[l],B[k-l]);  
    return ((la+lb)%2==0)? ((double)res1+(double)res2)/2 : (double)res1;  
   }  

No comments:

Post a Comment