2

2 つの配列があるとします。

2 5 6 4 3 7 1
5 1 6 2 3 7 4

両方の配列で前x, yの条件を満たす要素の数を数えます。xy

これまでの進捗状況:

配列をインデックスで並べ替えます。例では、これは次のようになります。

                     object: 1 2 3 4 5 6 7
indexes in the first array:  6 0 4 3 1 2 5
indexes in the secnod array: 1 3 4 6 0 2 5

各タプルを別のタプルと比較します。タプルのa両方のインデックスがタプルより低いか高い場合b、条件を満たす要素の数を増やします。

これには (N^2)/2 の時間の複雑さがあるため、O(N^2) となり、遅すぎます。最悪のシナリオの複雑さがこれ以上ないことは理解していますが、主に平均的な結果に関心があります。だから：より良い方法/アルゴリズムはありますか？

私は推移的なプロパティを使用することを考えました（両方が条件(x,y)を満たしている場合は、それも満たしています）が、うまくいきませんでした。(y,z)(x,z)

テストケース

配列の場合:

2 5 6 4 3 7 1
5 1 6 2 3 7 4

条件を満たすペアは次のとおりです。

(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7)

配列の場合:

1 2 3 4 5 6 7
1 2 3 4 5 6 7

条件を満たすペアは次のとおりです。

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7)
4

1 に答える 1

1

この問題について考えるのはとても楽しかったです。CS の宿題のように感じるので、すべてを解決することなく概念に触れてみます。

ビーチボーイズの原則

私の微積分の先生が使った用語で、実際に非常に応用できる問題解決テクニックです。基本的に、難しい問題を抱えている場合は、「...だったらいいのに」と言って、物事を簡単にする何かがあるかどうかを確認します. ある場合は、そのようにできるかどうかを確認してください。

この場合、一番上の配列が順序付けられていて、ただ[1, 2, 3 ...]. これにより、2 つの配列の問題が 1 つの配列の問題に変わるため、この問題の解決が非常に簡単になります。

まあ、そうかもしれません！これらの問題のいずれかを、順序付けされた最初の配列を持つ問題にマップできます。

リストした最初の例：

2 5 6 4 3 7 1
5 1 6 2 3 7 4

上記の問題は以下の問題と同等であると私は主張します。

1 2 3 4 5 6 7
2 7 3 1 5 6 4

マッピング

2->1 5->2 6->3 4->4 3->5 7->6 1->7 の単純な暗号置換を行うだけです (なぜこの特定のマッピングが行われるのでしょうか?)。これにより、問題の根底にある構造は同じままになります。これを解決してから、マッピングを元に戻すことができます。

1 つの問題をより単純な問題にマッピングするこの手法は、コンピューター サイエンス、特にアルゴリズムや計算可能性のクラスでよく使われます。

これで、すべてのペアを見つけるための単一の配列の問題が発生しました。

2 7 3 1 5 6 4

この時間の複雑さについては、読者に演習を任せます。

PS マッピングを元に戻す時間の複雑さを忘れないでください。マッピングの構築と分解には非常にコストがかかり、設計図に戻る必要があることが簡単にわかるだろうと考えて、問題を解決することがあります。

于 2016-10-09T20:19:24.407 に答える