有两个大小分别为m和n的排序数组a和b。找到两个排序数组的中值。总的运行时间复杂度应该是O（log（m+n））。
我不懂计算体重指数和体重指数的公式这些公式背后的逻辑是什么？
int aMid=aLen*k/（aLen+bLen）；//a的中间数
int bmid=k-amid-1；//b的中间数
这是程序的链接。
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/][1]
public static double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
if ((m + n) % 2 != 0) // odd
return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
else { // even
return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1)
+ findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
}
}
public static int findKth(int A[], int B[], int k,
int aStart, int aEnd, int bStart, int bEnd) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
// Handle special cases
if (aLen == 0)
return B[bStart + k];
if (bLen == 0)
return A[aStart + k];
if (k == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aMid = aLen * k / (aLen + bLen); // a's middle count
// I AM STUCK HERE
int bMid = k - aMid - 1; // b's middle count
// make aMid and bMid to be array index
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
我从代码的注释中得到了一些想法，这些公式是如何计算的，但是我还是不明白为什么要向别人解释“为什么要使用这些公式”，或者这些公式背后的逻辑是什么？
对于int-aMid=aLen*k/（aLen+bLen）；//a的中间数
如中间=alen/2--（i）
k=（alen+blen）/2，-->2=（alen+blen）/k
将2的值放入equ（i）
所以中间值=alen/（alen+blen）/k==alen*k/（alen+blen）
对于int bMid=k-aMid-1；//b的中间数
当a[amid]>b[bmid]时，必须满足amid+bmid+1=k才能得出结论。
至于为什么amid+bmid+1=k是显著的：如果a[amid]大于b[bmid]，你知道a中a[amid]之后的任何元素都不能是第k个元素，因为b中有太多元素低于它（并且会超过k个元素）。你也知道b[bmid]和b中b[bmid]之前的任何元素都不能是第k个元素，因为a中低于b[bmid]的元素太少（b[bmid]之前的元素不足以成为第k个元素）。
最佳答案
如您所述：aMid + bMid + 1 = k必须满足于能够得出以下结论：
当A[aMid] > B[bMid]我们可以扔掉bMid之前和aMid之后的所有东西，
因为我们知道有bMid+aMid+1（包括aMid）= k元素小于A[aMid]。因此我们的中位数在剩余的数组中。
考虑到这一点，我们如何设置两个中间值aMid和bMid并不重要唯一要注意的是不要让其中一个引起IndexOutOfBoundsException。
int aMid = 0;
int bMid = k - aMid - 1;
if(bMid >= bLen) {
bMid = bLen - 1;
aMid = k - bMid - 1;
}
也能做到。但这将需要超过
O(log(n+m))的时间，因为在最坏的情况下，我们总是跳过一个元素（A[0]）。我们想要的是永远扔掉一部分
aLen + bLen。在我们的案例中，这是：
a>b:k=k-（bmid+1）=k-（k-中间）=amid=k*（alen/（alen+blen））
b>a:k=k-（中间+1）=k-（k*alen/（alen+blen））-1=k*（blen/（alen+blen））-1
忽略-1并假设
A > B的概率与B > A相同，我们得到：E(k) = 0.5 * k * (aLen/(aLen + bLen)) + 0.5 * k * (bLen/(aLen + bLen))= 0.5 * k (aLen + bLen)/(aLen + bLen) = 0.5 * k意思是我们得到大约
O(log(n + m))递归调用，直到k为0，然后函数停止。关于java - 了解两个排序数组中位数的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34103511/