LeetCode, Median of Two Sorted Arrays, Java Solution, O(m+n), O(log(m+n))

Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 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)).

O(m+n), merge solution.

/**
*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)).
*/
public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
    	if(A.length==0&&B.length==0) return -1.0;
    	if(A.length==0) {
    		if(B.length%2==1){
    			return B[B.length/2];
    		}
    		return 0.5*(B[B.length/2]+B[B.length/2-1]);
    	}
    	if(B.length==0){
    		if(A.length%2==1){
    			return A[A.length/2];
    		}
    		return 0.5*(A[A.length/2]+A[A.length/2-1]);
    	}

    	int len=A.length+B.length;
    	boolean isEven=false;
    	int C[]=new int[len/2+1];
    	int a=0,b=0;

    	for(int i=0;i<C.length;i++){
    		if(a>A.length-1){
    			C[i]=B[b];
    			b++;
    		}else if(b>B.length-1){
    			C[i]=A[a];
    			a++;
    		}else{
    			if(A[a]<B[b]){
    				C[i]=A[a];
    				a++;
    			}else{
    				C[i]=B[b];
    				b++;
    			}
    		}

    	}
    	for(int i=0;i<C.length;i++){
    		System.out.print(C[i]);
    	}
    	System.out.println();
    	if(len%2==1) return C[C.length-1];
    	return 0.5*(C[C.length-1]+C[C.length-2]);
    }

}

O(log(m+n))

public class Solution {
  // using divide and conquer idea, each time find the mid of both arrays


public double findMedianSortedArrays(int A[], int B[]){
    return findMedianSortedArrays(A,A.length,B, B.length);
}






public double findMedianSortedArrays(int A[], int m, int B[], int n) {
        /* A[0, 1, 2, ..., n-1, n] */
        /* A[0, 1, 2, ..., m-1, m] */
        int k = (m + n + 1) / 2;
        double v = (double)FindKth(A, 0, m - 1, B, 0, n - 1, k);


        if ((m+n) % 2 == 0) {
            int k2 = k+1;
            double v2 = (double)FindKth(A, 0, m - 1, B, 0, n - 1, k2);
            v = (v + v2) / 2;
        }


        return v;
    }


    // find the kth element int the two sorted arrays
    // let us say: A[aMid] <= B[bMid], x: mid len of a, y: mid len of b, then wen can know
    // 
    // (1) there will be at least (x + 1 + y) elements before bMid
    // (2) there will be at least (m - x - 1 + n - y) = m + n - (x + y +1) elements after aMid
    // therefore
    // if k <= x + y + 1, find the kth element in a and b, but unconsidering bMid and its suffix
    // if k > x + y + 1, find the k - (x + 1) th element in a and b, but unconsidering aMid and its prefix
public   int FindKth(int A[], int aL, int aR, int B[], int bL, int bR, int k) {
        if (aL > aR) return B[bL + k - 1];
        if (bL > bR) return A[aL + k - 1];


        int aMid = (aL + aR) / 2;
        int bMid = (bL + bR) / 2;


        if (A[aMid] <= B[bMid]) {
            if (k <= (aMid - aL) + (bMid - bL) + 1) 
                return FindKth(A, aL, aR, B, bL, bMid - 1, k);
            else
                return FindKth(A, aMid + 1, aR, B, bL, bR, k - (aMid - aL) - 1);
        }
        else { // A[aMid] > B[bMid]
            if (k <= (aMid - aL) + (bMid - bL) + 1) 
                return FindKth(A, aL, aMid - 1, B, bL, bR, k);
            else
                return FindKth(A, aL, aR, B, bMid + 1, bR, k - (bMid - bL) - 1);
        }
    }
}

both of two solution are super slow.

One possible solution is a variant of  binary search. The idea is.

m=A.length, n=B.length, m>n. Find the median of A, which is at m/2. And get the number in B that smaller than A(m/2) by binary search. The outer loop is o(log(m)), the inner loop is O(log(n)), the whole solution is O(log(m+n)). Here is