K インデックスで配列を反時計回りに回転する範囲合計クエリ用の JavaScript プログラム

配列の反時計回りの回転は、指定された配列のすべての要素を指定されたインデックス数だけ左に回転することを意味します。この記事では、配列を k インデックス分反時計回りに回転する範囲合計クエリ用の JavaScript プログラムを実装します。

問題の紹介

この問題では、いくつかの整数を含む配列と、ペアの形式で値を含む別の配列が与えられます。各ペアは現在のクエリに必要な回転数になります。指定された回転数の後、範囲が取得され、その指定された範囲内に存在する要素の合計を答える必要があります。例えば、＃＃＃

例 1 リーリー

イラスト

回転数は3なので、3回回転後の配列は4 5 6 1 2 3となります。

1 ～ 4 の範囲の要素は 5、6、1、2 です。したがって、合計は 14 になります。

例 2 リーリー

イラスト

回転数は 8 なので、8 回転後の配列は 8 % (配列の長さ) の回転に等しくなります。配列の長さの回転の後、同じ配列が再び表示されるため、8 回転は 2 回転に相当します。

したがって、8回回転後の配列は3 4 5 6 1 2となります。

この範囲では、0 ～ 3 の要素はそれぞれ 3、4、5、6 になります。したがって、合計は 18 になります。

単純な方法

単純なアプローチでは、配列のクエリで説明されているすべての手順を単純に実行します。同様に、配列を回転するように指定され、配列要素を指定された回数だけ回転して、範囲内の要素の合計をチェックします。コードを見てみましょう -

＃＃＃例＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(Q*N) です。ここで、Q はクエリの数、N は配列のサイズです。

サイズ N の新しい配列を作成しているため、上記のコードの時間計算量は O(N) です。

プレフィックス合計方法

プレフィックス合計メソッドでは、プレフィックス合計配列を作成します。プレフィックス合計配列の各インデックスには、現在のインデックスまでのすべての要素の合計が含まれます。コードを見てみましょう -

＃＃＃例＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(Q) です。ここで、Q はクエリの数です。

配列要素のプレフィックスの合計を格納する新しい配列を作成しているため、上記のコードの時間計算量は O(N) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、配列を k インデックスずつ反時計回りに回転する範囲合計クエリ用の JavaScript プログラムを実装しました。配列の反時計回りの回転は、指定された配列のすべての要素を指定されたインデックス数だけ左に回転することを意味します。まず、時間計算量が O(Q*N) の単純な方法と、時間計算量が O(Q) のプレフィックス合計方法の 2 つの方法を実装しました。

以上がK インデックスで配列を反時計回りに回転する範囲合計クエリ用の JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。