指定された配列のサイズ 3 の反転を計算する JavaScript プログラム

このチュートリアルでは、指定された配列のサイズ 3 の反転を計算する方法を学びます。

問題ステートメント - 個別の数値エントリを含む長さ n の配列が与えられます。 arr[i] > arr[j] > arr[k] (I

ここでは、まず総当たり法を学習し、次にその時間と空間の複雑さを最適化します。

ブルートフォース手法を使用する

ブルート フォース アプローチでは、3 つのネストされた for ループを使用して、サイズ 3 のカウント反転を見つけます。最初のループは 1 番目の要素から n-2 番目の要素まで繰り返し、2 番目のループは i 番目の要素から n-1 番目の要素まで繰り返します。前の要素が次の要素より大きい場合は、配列を反復処理して、中央の要素より小さい要素を見つけます。

＃＃＃文法＃＃＃

ユーザーは、以下の構文に従って総当たり法を使用して、指定された配列のサイズ 3 の反転を計算できます。

リーリー ＃＃＃アルゴリズム＃＃＃

ステップ 1

- for ループを使用して、最初の n-2 要素を繰り返します。

• ステップ 2
- ネストされた for ループを使用して、m 1 から len-1 個の要素を繰り返します。

• ステップ 3
- ネストされた for ループで、array[m] が array[n] より大きいかどうかを確認します。その場合、n 番目の要素から最後の要素まで繰り返します。

• ステップ 4
- o 番目のインデックスの要素が n 番目のインデックスの要素より小さい場合、サイズ 3 の有効な反転ペアが見つかったと言え、その値を大きくします。 「cnt」変数は 1 減算されます。

• ステップ 5
- for ループのすべての反復が完了したら、「cnt」の値を返します。

• 例 1

以下の例では、サイズ 3 の反転ペアの総数を見つけるために総当たり法を実装します。

指定された配列では、ユーザーは出力で 2 つの反転ペアのみを確認できます。最初の反転ペアは (10,5,4) で、2 番目の反転ペアは (20,5,4) です。

リーリー

時間と空間の複雑さ

時間計算量

- 3 つのネストされた for ループを使用するため、時間計算量は O(n^3) です。

• 空間複雑度
- 一定空間を使用する場合、空間複雑度は O(1) です。

• ネストされた 2 つの for ループを使用する

このメソッドでは、2 つのネストされたループを使用します。現在の要素の右側にある小さい要素の合計数と、左側にある大きい要素の合計数を見つけます。その後、この 2 つを乗算して、特定の数値の反転の合計数を取得します。

＃＃＃文法＃＃＃

ユーザーは、以下の構文に従って、JavaScript で 2 つのネストされたループを使用してサイズ 3 の反転を計算できます。

リーリー ＃＃＃アルゴリズム＃＃＃

ステップ 1

- for ループを使用して、配列の n 要素を繰り返します。

• ステップ 2

  - for ループを使用して、現在の要素の右側にある、現在の要素より小さい要素をすべて検索します。

• ステップ 3

  - for ループを再度使用して、現在の要素の左側にある、現在の要素より大きい要素をすべて検索します。

• ステップ 4

  - 左右の変数の値を乗算し、「cnt」変数に追加します。

例 2

• 次の例では、上記の方法で示したように、2 つのネストされたループを使用して、サイズ 3 の反転の合計数を見つけます。ユーザーは、出力が最初の方法と同じであることを確認できます。 リーリー 時間と空間の複雑さ

時間計算量

- 2 つのネストされたループを使用するため、上記の方法の時間計算量は O(n^2) です。

• 空間複雑度

  - 一定空間を使用する場合、空間複雑度は O(1) です。

ユーザーは、指定された配列内でサイズ 3 の反転数を見つける 2 つの方法を学習しました。最初のアプローチでは、総当たりアプローチを使用して問題を解決し、2 番目のアプローチでは、時間の複雑さを軽減するためにソリューションをさらに最適化しました。

以上が指定された配列のサイズ 3 の反転を計算する JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。