2014年5月13日星期二

Binary Solution - Median of Two Sorted Arrays ?

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

    public double median(int[] a, int i, int j, int[] b) {
        if (j  > valueAt(b, i*b)) {
            return median(a, i, i*a, b);
        } else if (valueAt(a, i*a) < valueAt(b, i*b - 1)) {
            return median(a, i*a + 1, j, b);
        } else {
            return (a.length + b.length) % 2 == 1 ? valueAt(a, i*a):
                (valueAt(a, i*a) + Math.max(valueAt(a, i*a - 1), valueAt(b, i*b - 1))) / 2.0;
        }
    }

    public int valueAt(int[] arr, int i) {
        if (i = arr.length) return Integer.MAX_VALUE;
        else return arr[i];
    }
}

没有评论: