配列要素の周波数範囲をクエリするための Javascript プログラム

整数を含む配列とクエリを含む別の配列を取得します。各クエリは、配列内の左端と右端のインデックスと 1 つの要素によって指定される範囲を表します。その範囲または部分配列について、その範囲内の特定の要素の出現頻度を見つける必要があります。

要素の頻度は、範囲内に存在する各整数が何回出現するかを伝える必要があることを意味します。例えば ​​-＃＃＃

指定された配列が [5, 2, 5, 3, 1, 5, 2, 2, 5]

の場合

クエリ配列は: [[0, 4, 5], [1, 7, 2]]

• 最初のクエリの場合、部分配列は 5、2、5、3、1 であるため、5 の頻度は 2 になります。

• 2 番目のクエリの場合、部分配列は 2、5、3、1、5、2、2 であるため、2 の頻度は 3 になります。

＃＃＃方法＃＃＃

この問題を解決するには、次の手順に従います -

まず、各クエリを呼び出し、クエリ要素をパラメータとして渡す個別の関数を作成します。

• 関数内で、反復する配列の長さを取得し、指定された要素の頻度を格納する変数 count を作成します。

• for ループを使用して指定された範囲を反復し、各反復で現在の配列要素が指定された要素と等しい場合、カウントをインクリメントします。

• 最後に、指定された要素の現在の数を出力します。

• ＃＃＃例＃＃＃

  理解を深めるために、上記の手順を実装するための正しいコードを見てみましょう -
リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(Q*N) です。ここで、Q はクエリの数、N は配列のサイズです。クエリごとに指定された範囲内の配列を反復処理するため、時間計算量は N 倍になります。

上記のコードのスペース複雑さは O(1) です。これは、何も保存するために余分なスペースを使用していないためです。

＃＃＃特別なケース＃＃＃

上記のコードでは、O(Q*N) の時間計算量を取得します。指定された配列に存在するさまざまな要素の数が、各要素の個別の配列の数よりも少ない場合、空間計算量は次のようになります。時間の複雑さを改善したり、プレフィックス合計のマッピングを維持したりするために、 によって計算されます。

しかし、このメソッドは多くのスペースを消費し、その複雑さは O(D*N) です。ここで、D は配列内に存在するさまざまな要素の数、N は配列の長さです。

プレフィックスの合計を維持することにより、任意のクエリに対する答えを O(1) 時間で与えることができ、全体の時間計算量は O(Q) になります。ここで、Q はクエリの数です。

＃＃＃例＃＃＃ リーリー ＃＃＃結論は＃＃＃

このチュートリアルでは、範囲クエリに応答して、各クエリで指定された範囲内の特定の要素の頻度を返す JavaScript プログラムを実装しました。配列内の指定された範囲を反復処理し、カウントを取得する変数を維持しました。上記のコードの時間計算量は O(Q*N)、上記のコードの空間計算量は O(1) です。

以上が配列要素の周波数範囲をクエリするための Javascript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。