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, 继续这个过程