ソートされたバイナリ配列の 1 を数える Javascript プログラム

ソートされたバイナリ配列で 1 を数える方法は 2 つあります。 1 つ目は、配列を反復処理して 1 の数をカウントすることです。 2 番目の方法は、二分探索アルゴリズムを使用して、配列内で最初に出現する 1 を見つけることです。

これらのメソッドを使用するには、配列をソートする必要があることに注意してください。

このブログ投稿では、ソートされたバイナリ配列内の 1 の数を数える JavaScript プログラムについて説明します。また、プログラムをより効率的にするためのいくつかの特殊なケースと最適化手法についても見ていきます。

＃＃＃＃＃＃問題文＃＃＃＃＃＃

ソートされたバイナリ配列が与えられた場合、タスクは配列内の 1 の数をカウントすることです。配列は任意のサイズにすることができ、その要素は 0 または 1 のみにすることができます。 ＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 方法1

最初に思いつく方法は、配列を反復処理して 1 の数を数えるというものです。

カウント変数を初期化して、配列に数値を格納します。

配列を反復処理して、各要素を確認します。現在の要素が 1 に等しい場合、カウンターをインクリメントします。

• ＃＃＃例＃＃＃ リーリー

  ただし、配列全体を 1 回繰り返す必要があるため、このメソッドの時間計算量は O(n) です。n は配列のサイズです。

これは、配列がソートされているという事実を利用することで最適化できます。

• 方法 2

配列内の 1 の最初のインスタンスを見つけるには、二分探索法を使用します。配列内の項目の総数から最初の 1 インスタンスのインデックスを引くだけで、1 の数が得られます。

この実装では、「最初の出現」バイナリ検索手法を使用して、配列内の 0 の最初のインスタンスを見つけます。

low 変数と high 変数は、最初はそれぞれ配列の最初と最後のインデックスに設定されます。

配列内の項目の数は、firstOne という名前の変数の値としても指定されます。この変数は、数値 1 の最初のインスタンスのインデックスを記録するために使用されます。
while ループは、低いインデックスが高いインデックス以上になるまで実行され続けます。各反復の後、現在の範囲の中点を決定します。
中央の要素が 1 の場合、firstOne 変数を更新し、上位のインデックスを前の要素に移動します。中間点の要素が 0 の場合、下位のインデックスを後続の要素に移動します。
while ループが完了したら、最初の変数が配列の -1 値に対応するかどうかを確認します。そうである場合は、配列に 1 がないことを意味するため、1 が返されます。そうでない場合は、firstOne から arr.length を引いた値を返します。

• ＃＃＃例＃＃＃ リーリー
この方法の時間計算量は O(log n) で、前の方法よりもはるかに効率的です。

• このチュートリアルでは、ソートされたバイナリ配列内の 1 の数を数える JavaScript プログラムについて説明しました。

以上がソートされたバイナリ配列の 1 を数える Javascript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。