4

これを手伝ってくれませんか。：「AとBを自然数の増分配列とし、Kを任意の自然数とします。A[i] + B [j] =となるようなインデックス（i、j）のすべての可能なペアを決定する効果的なアルゴリズムを見つけます。 K.アルゴリズムの正しさを証明し、その複雑さを推定します。」

最初の配列を繰り返し処理して、もう一方の配列でバイナリ検索を実行する必要がありますか？ありがとう ：）

4

4 に答える 4

6

いいえ！

両方の配列が順序付けられているため、次のようにします。

  • itAの先頭にイテレータを配置しますA
  • itBの最後にイテレータを配置しますB
  • イテレータを反対方向に移動*itA + *itBし、各反復でテストします。値がに等しい場合はK、両方のインデックスを返します。値が、より小さい場合はK、増分しますitA。それ以外の場合は、デクリメントしますitB。

両方の配列を通過すると、線形時間で完了します。

于 2012-10-24T22:42:04.897 に答える
1

すべてのA[i]に対して1つのB[j]しか存在できないため、O（n + m）の複雑さの解を見つけることができます。（A [i1] B [j1]）と（A [i2] B [i2]）が両方とも正しいペアであり、i1がi2より小さい場合、j1はj2より大きくなければならないという事実に頼ることができます。お役に立てれば。

于 2012-10-24T22:43:32.227 に答える
0

それが役立つかどうかはわかりませんが、それは単なるアイデアです。Aを線形および二分探索Bにループしますが、Aを逆方向に実行します。これにより、Aの各ステップでBの一部を除外できるため、より良い最良のケースが得られる可能性があります。

A[i]がKを解くためにB[42]と言う必要があることがわかっている場合、A[i-1]には少なくともB[43]以上が必要であることがわかります。

編集：Bの要素がAより少ない場合は、それを裏返し、代わりにBを線形に実行することも追加したいと思います。

于 2012-10-24T22:41:37.573 に答える
0

C ++で可能な実装は、次のようになります。

#include <iostream>
int main()
{
    int A[]={1,2,3,6,7,8,9};
    int B[]={0,2,4,5,6,7,8,12};

    int K=9;
    int sizeB=sizeof B/sizeof(int);
    int sizeA=sizeof A/sizeof(int);


    int i=0;
    int j=sizeB-1;
    while(i<sizeA && j>=0)
    {
        if ((A[i]+B[j])==K){
            std::cout << i<<","<<j<< std::endl;
            i++;
            j--;
        }
        else if((A[i]+B[j])<K){
            i++;
        }
        else{
            j--;
        }
    } 
    return 0;
}
于 2013-11-09T00:30:29.307 に答える