3

サイズがそれぞれ m と n の 2 つの並べ替えられた配列 A と B があります。2 つの並べ替えられた配列の中央値を見つけます。全体的な実行時間の複雑さは 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)質問: chooseとはどういう意味ですか?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) は false になり、アルゴリズムはうまく機能するはずです。
m<n の場合、ヘルパー内で (l>r) は false になり (m=1 でない限り)、「修正」は何も修正しないようです。

したがって、コードの最初に何か問題があると思います。
ただし、主要部分は私にとっては理にかなっているようで、実際に Java で同じことを行うための実装に役立ちました。

于 2012-10-18T18:13:49.017 に答える
0

質問 > l = max(0, (mn)/2) および 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

http://leetcode.com/2011/03/median-of-two-sorted-arrays.html このアルゴリズムの分析の詳細はこちら

于 2014-01-14T01:49:35.087 に答える
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 が結合された中間要素になります。したがって、2 つの配列 (A/2 と B/2) で要素を検索し続ける必要があるため、配列が等しくなるまで 1) 項目に進みます。
于 2013-04-07T14:16:02.607 に答える