Accepted Java solution with O(log(min(n,m)) iterations.


  • 2
    P

    The idea is to move median carrige inside the smaller array and than in the larger for the same number of steps but in oposite side. For example if candidate for median in smaler array in greater than in candidate for median in larger than move carrige to left in smaler array and for the same number of steps to right in larger array. If candidate in smaller array in less than candidate in larger array than move to righnt in smaller and to left in larger. The hardes part for me in that idea was to get final result taking into accout all edge cases.

    public double findMedianSortedArrays(int A[], int B[]) {
    	if (A.length == 0) return median(B);
    	if (B.length == 0) return median(A);
    	if (A.length < B.length) {
    		return median(A, 0, A.length-1, B);
    	} else {
    		return median(B, 0, B.length-1, A);
    	}
    }
    
    private double median(int[] A, int leftA, int rightA, int[] B) {
    	// Move median indices in A and B arrays
    	int midA = (rightA + leftA)/2;
    	int midB = (B.length-1)/2 - midA + (A.length-1)/2;
    	
    	// Get the final result.
    	//
    	// I was started to became crazy of all if()else 
    	// conditions when trying to catch all edge cases.
    	// And decided simply to put all possible candidates
    	// to be the median in a small array. Than sort and get
    	// the median of that small array :).
    	if (rightA-leftA <= 1) {
    		boolean evenA = (A.length&1)==1;
    		boolean evenB = (B.length&1)==1;
    		int[] a = new int[(evenA ? 5 : 4) + (evenB ? 5 : 4)];
    		int j = 0;
    		for (int i = (evenA ? -2 : -1); i < 3; i++) {
    			a[j++] = (midA+i < 0) ? Integer.MIN_VALUE : midA+i > A.length-1 ? Integer.MAX_VALUE : A[midA+i];
    		}
    		for (int i = (evenB ? - 2 : -1); i < 3; i++) {
    			a[j++] = (midB+i < 0) ? Integer.MIN_VALUE : midB+i > B.length-1 ? Integer.MAX_VALUE : B[midB+i];
    		}
    		Arrays.sort(a);
    		return median(a);
    	}
    	
    	// Recursion. log(min(n,m)) 
    	if (A[midA] > B[midB]) {
    		return median(A, leftA, midA, B);
    	} else {
    		return median(A, midA, rightA, B);
    	}
    }
    
    private double median(int[] A) {
    	int len = A.length;
    	return (len&1)==1 ? A[(len-1)/2] : (A[(len-1)/2] + A[(len-1)/2+1])/2.;
    }

Log in to reply
 

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