algorithm - 在两个排序数组的合并数组中查找中位数

Question

假设我们有 2 个排序的整数数组，大小分别为 n 和 m。查找所有 m + n 数字的中位数的最佳方法是什么？

log(n) * log(m) 复杂度很容易做到这一点。但我想在 log(n) + log(m) 时间内解决这个问题。那么有什么建议可以解决这个问题吗？

Answer 1

解释

这道题的重点是通过比较剩下的A和B的中位数，每一步递归忽略掉A和B的一半:

if (aMid < bMid) Keep [aMid  +1 ... n] and [bLeft ... m]    
else Keep [bMid + 1 ... m] and [aLeft ... n]
// where n and m are the length of array A and B

如下:时间复杂度为O(log(m + n))

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length, n = B.length;
    int l = (m + n + 1) / 2;
    int r = (m + n + 2) / 2;
    return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
}

public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
    if (aStart > A.length - 1) return B[bStart + k - 1];            
    if (bStart > B.length - 1) return A[aStart + k - 1];                
    if (k == 1) return Math.min(A[aStart], B[bStart]);

    int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
    if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        

    if (aMid < bMid) 
        return getkth(A, aStart + k / 2, B, bStart, k - k / 2); // Check: aRight + bLeft 
    else 
        return getkth(A, aStart, B, bStart + k / 2, k - k / 2); // Check: bRight + aLeft
}

希望对您有所帮助!如果您需要对任何部分进行更多解释，请告诉我。