3

有两个大小分别为 m 和 n 的排序数组 A 和 B。找到两个排序数组的中位数。总体运行时间复杂度应为 O (log (m+n))。

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    return findMedianHelper2(A, m, B, n, max(0, (m-n)/2), min(m-1, (m+n)/2));
}

double findMedianHelper2(const int A[], const int m, const int B[], const int n, const int l, const int r) {
    if (l > r) return findMedianHelper2(B, n, A, m, max(0, (n-m)/2), min(n-1, (m+n)/2));

    int i = (l+r)/2;
    int j = (m+n)/2-i;

    assert(i >= 0 && i <= m && j >= 0 && j <= n);
    int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
    int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
    int Ai = ((i == m) ? INT_MAX : A[i]);
    int Bj = ((j == n) ? INT_MAX : B[j]);

    if (Ai < Bj_1) return findMedianHelper2(A, m, B, n, i+1, r);
    if (Ai > Bj) return findMedianHelper2(A, m, B, n, l, i-1);

    if (((m+n) % 2) == 1) return A[i];
    return (max(Ai_1, Bj_1) + Ai) / 2.0;
}

问题：选择l = max(0, (m-n)/2)和是什么意思r = min(m-1, (m+n)/2)

谢谢

4

5 回答 5

1

那个代码对我来说没有意义。但是，我认为这里的关键是确保 m>n 和值 (mn)/2 和 (m+n)/2 正确传递给辅助函数。此外，从辅助函数开头的 if 语句中，我们可以看出其意图是在 m<n 时进行修复。

假设 m>0 和 n>0（它们必须如此才能使数组有意义。）
如果 m>n，那么在辅助函数内部，(l>r) 将为假，并且算法应该运行良好。
如果 m<n，那么在帮助器内部， (l>r) 将为假（除非 m=1），并且“修复”似乎根本无法修复任何东西。

因此，我认为代码一开始就有问题。
但是，主要部分对我来说似乎很有意义，并且确实帮助我实现了在 JAVA 中做同样的事情。

于 2012-10-18T18:13:49.017 回答
0

问题 > 选择 l = max(0, (mn)/2) and r = min(m-1, (m+n)/2) 是什么意思

MAX 和 MIN 用于限制值，因此它们不能低于或高于约束。

IF m - n < 0 THEN
    l = 0
ELSE l = (m - n) / 2

IF (m + n) / 2 > m - 1 THEN
    r = m -1
ELSE r = (m + n) / 2
于 2012-09-25T14:36:27.520 回答
0

首先。让我们证明 m=n 情况下的算法。将中间元素命名为“k”

  • m1:=A[n/2]

    m2:=B[n/1]`

    如果 m1 < m2，则 m1 < k < m2，否则 m2 < k < m1。

    证明：m1 < k 所以让 m2 < k 但它不正确：“k”元素索引明显高于 n。因此 m2 > k。

如果 m1 > k 与我们得到 m2 < k 的方式相同。

  • A 和 B 合并的中间元素将以相同的方式成为 A/2 和 B/2 合并的中间元素。所以我们需要继续在两个数组中查找元素：A/2 和 B/2 所以转到 1) 项，直到数组相等。
于 2013-04-07T14:16:02.607 回答
0

选择这样的左右索引的原因是跳过不能是两个排序数组中位数的元素。

不失一般性，我们假设m > n。然后有两种极端情况：

  • 即使 B 中的所有元素都小于A[0]，中位数仍然不可能是其中的元素，A[0, ... , (m - n) / 2 - 1]因为n + (m - n) / 2 - 1 < (m + n) / 2。
  • 同样，即使 B 中的所有元素都大于 A[m - 1]，中位数仍然不可能是其中的元素，A[(m + n) / 2 + 1, ... , m - 1]因为A[(m + n) / 2]必须是中位数。

基于这个观察，我们只需要对较长数组的一个子数组进行二分查找，就可以找到中位数。

在 ,和的情况下m < n，这基本上意味着中位数可能是较短数组中的任何元素。l = max(0, (m-n)/2) = 0r = min(m-1, (m+n)/2) = m - 1

于 2014-08-03T02:44:28.757 回答
0

http://leetcode.com/2011/03/median-of-two-sorted-arrays.html 这里是这个算法的分析细节

于 2014-01-14T01:49:35.087 回答