ソートされた配列内の AP を形成するすべてのトリプルを出力する JavaScript プログラム

AP は、連続する 2 つの要素の差が常に同じである算術シーケンスです。素朴な方法、二分探索方法、および 2 ポインタ方法の 3 つの方法を使用して、AP を形成するソートされた配列内のすべてのトリプルを出力します。

問題の紹介

この質問では、ソートされた配列が得られます。これは、すべての要素が増加形式であることを意味します。配列内で 3 つの要素を見つけて AP を形成する必要があります。例えば ​​-＃＃＃

指定された配列: 1 5 2 4 3

隣接する要素間の差が等しいため、指定された配列から 2 つのトリプル (1 2 3 と 5 4 3) が得られます。また、書かれているように、トリプルを見つけるだけでよいので、それ以上長いシーケンスは見つかりません。

トリプルを見つける方法に移りましょう -

＃＃＃方法＃＃＃

単純な方法

このメソッドでは、ループを使用して配列上を移動し、反復ごとに別の配列を実行して、現在のインデックスと比較してより大きな数を取得します。次に、最初のネストされた配列内にネストされた配列を再度実装して、AP を形成できる要素を見つけます。コードを見てみましょう -

＃＃＃例＃＃＃ リーリー

上記のコードの時間計算量は O() で、N は配列のサイズです。

余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

簡単な方法に従ってください

前の方法では、要素が 2 つある場合、共通の違いがあるため 3 番目の要素を見つけることができます。そのため、3 番目の要素を見つけるには、線形検索を使用する代わりに二分検索を使用し、時間の複雑さを軽減できます。上記のコード-

＃＃＃例＃＃＃ リーリー

上記のコードの時間計算量は O() で、N は配列のサイズです。

余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

効率的な方法

このメソッドでは、2 つのポインターを使用して、現在位置と同じ差を持つ要素を見つけます。コードを見てみましょう -

＃＃＃例＃＃＃ リーリー

上記のコードの時間計算量は O(N*N) (N は指定された配列のサイズ)、余分なスペースを使用していないため、上記のメソッドのスペース計算量は O(1) です。

Note

- 最初の 2 つのメソッドは、ソート済みか未ソートのあらゆる種類の配列に有効ですが、最後のメソッドはソート済みの配列に対してのみ機能します。配列が未ソートの場合は、一方向にソートできます。または別の方法もありますが、それでもこの方法が他のすべての方法の中で最良です。

＃＃＃結論は＃＃＃

このチュートリアルでは、指定されたソートされた配列内の AP を形成するすべてのトリプルを出力する JavaScript プログラムを実装しました。 Ap は、連続する 2 つの要素の差が常に同じになる等差数列です。時間計算量 O(N*N*N) の単純な方法、時間計算量 O(N*N*log(N)) の二分探索方法、および 2 ポインター方法の 3 つの方法を見てきました。

以上がソートされた配列内の AP を形成するすべてのトリプルを出力する JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。