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

    public double findMedianSortedArrays(int[] A, int[] B) {
        if (A == null || B == null) {
            return -1; //or throw error
        }
        int size = A.length + B.length;
        if (size % 2 == 0) {
            return (findMedianHelper(A, 0, B, 0, size / 2) + findMedianHelper(A, 0, B, 0, size / 2 + 1)) / 2.0;
        } else {
            return findMedianHelper(A, 0, B, 0, size / 2 + 1);
        }
    }

    //find kth element from array A and B which starts from aStart and bStart
    public double findMedianHelper(int[] A, int aStart, int[] B, int bStart, int k) {
        if (aStart >= A.length) {
            return B[bStart + k - 1];
        }
        if (bStart >= B.length) {
            return A[aStart + k - 1];
        }
        if (k == 1) {
            return Math.min(A[aStart], B[bStart]);
        }

        int aPivot = aStart + k / 2 - 1 < A.length ? A[aStart + k / 2 - 1] : Integer.MAX_VALUE;
        int bPivot = bStart + k / 2 - 1 < B.length ? B[bStart + k / 2 - 1] : Integer.MAX_VALUE;

        if (aPivot < bPivot) {
            return findMedianHelper(A, aStart + k / 2, B, bStart, k - k / 2);
        } else {
            return findMedianHelper(A, aStart, B, bStart + k / 2, k - k / 2);
        }
    }

Follow Up Questions:

Now we have N machines, on each there is a sorted array, how to scale it to work together and efficiently find Kth element over all.

Solution 1:

N/2 group, each group has two machine. In each group, do only keep kth of two sorted array, then divide into n/4 groups, each group has 2 machine, keep kth of two sorted arrays again.

Time Complexity: O(K*lgN)

Solution 2:

二分答案S,将S广播给每台机器,每台机器用二分法求得有多少比该数小的数。汇总结果后可判断是该将S往上还是往下调整。总共最大的数是max, 最小的数是min,

s = (max+min)/2

然后你把s 拿到n台机器上去二分找有多少个数比他小, 如果有x个数比他小,

那么x< k 的话, min = s, x> k的话,max =s, 继续这个过程

FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *