Can some one help me improve my algorithm. Java, 400+ms.


  • 2
    C

    My thought is very straight forward. Just cut A or B half and half and half until one of them be empty array.
    My algorithm

    public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int length_A=A.length;
        int length_B=B.length;
        int mid=(length_A+length_B)/2;
        //if length of array A + length of array B is even, the median is the average of the mid two number.
        if(((length_A+length_B)&1)==0)return (fi(A,B,mid,0,length_A-1,0,length_B-1)+fi(A,B,mid+1,0,length_A-1,0,length_B-1))/2.0;
        //if the number of element of A+B is odd, the median is the mid number.
        else return fi(A,B,mid+1,0,length_A-1,0,length_B-1);
    }
    
    //the method is used to find the i's largest number of array A and B; i is the i's largest number.
    //a1,b1 stand for the start pointer of array A and array B;
    //a2,b2 stand for the end pointer of array A and Array B;
    
    public double fi(int A[], int B[], int i, int a1, int a2, int b1, int b2)
    {
        if(a2-a1<0)return B[b1+i-1];
        if(b2-b1<0)return A[a1+i-1];
        int ma=(a1+a2)/2;
        int mb=(b1+b2)/2;
        if(A[ma]<=B[mb]){
            if(i<=ma-a1+1+mb-b1)return fi(A,B,i,a1,a2,b1,mb-1);
            else return fi(A,B,i-ma+a1-1,ma+1,a2,b1,b2);
        }
        else{
            if(i<=mb-b1+1+ma-a1)return fi(A,B,i,a1,ma-1,b1,b2);
            else return fi(A,B,i-mb+b1-1,a1,a2,mb+1,b2);
        }
    }}
    

    is there someone could help me improve it to O(log(m+n)) I will appreciate it.


Log in to reply
 

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