最小の欠損値を見つけるための JavaScript プログラム

さまざまな非負の整数のソートされた配列が与えられるので、欠落している最小の数値を見つける必要があります。したがって、このチュートリアルでは、この問題を解決するさまざまな方法を検討し、さまざまな例を使用してその時間計算量について説明します。

質問を理解する

問題の説明は非常に簡単です。さまざまな非負の整数のソートされた配列が与えられた場合、その中で欠損している最小の数値を見つける必要があります。この問題を理解するために例を挙げてみましょう。

配列 [1, 2, 4, 5, 6] があるとします。ここで、この配列の数値 2 と 4 の間にスペースがあることがわかります。この不一致は、数値が欠落していることを示します。次に、その位置に適合する最小の数値を見つける必要があります。

数値が欠落しているかどうかを判断するには、まず配列に数値 3 が含まれているかどうかを確認する必要があります。数値 3 が配列に存在しない場合、数値 3 が配列に含まれていないため、それは欠落している数値であると言えます。

次に、この問題を解決するいくつかの方法を見てみましょう。

方法 1: 素朴な方法

この問題を解決する最も簡単な方法の 1 つは、配列をループして各項目が正しい位置にあることを確認することです。要素が正しい位置にない場合は、欠落している要素の最小数を見つけます。

これは上で説明したコードです -

配列全体を走査する必要があるため、このメソッドの時間計算量は O(n) です。

ただし、この解決策は、ソートされた配列が提供されるという事実を利用していないため、非効率的です。

方法 2: 二分探索法

ここでは、この問題をより効率的に解決するために二分探索法を使用します。このメソッドでは、配列内に存在しない最初の要素に対して二分検索を実行します。このメソッドのコードは -

二分探索を行っているため、上記の方法の時間計算量は O(log n) です。

この方法は、配列がソートされるという事実を利用するため、単純な方法よりも効率的です。

方法 3: 線形探索方法

これから説明する 3 番目の方法は、線形探索方法です。この方法は、配列がソートされているという事実に依存しており、これにより線形検索を適用して欠落している数値を特定できるようになります。

線形検索方法は、配列を反復処理し、各メンバーをそのインデックスと比較することによって機能します。要素のインデックスがその値と等しくない場合、欠落している要素は配列内のその要素の前の別の場所にあります。欠落している要素のインデックスを返します。

線形探索法のコードは次のとおりです -

配列全体を反復する必要があるため、このメソッドの時間計算量は O(n) です。

この方法は二分探索法よりも効率が劣りますが、小さな配列には便利です。

方法 4: 二分検索の改善

これから説明する 4 番目の方法は、改良された二分探索方法です。このメソッドは、中間要素を欠落している整数と比較する代わりに、そのインデックスと比較することを除いて、バイナリ検索メソッドと非常によく似ています。

修正された二分探索法の背後にある基本的な考え方は、各ステップで配列を半分に分割し、中央の要素をそのインデックスと比較することです。中央の要素がそのインデックスより大きい場合、欠落しているメンバーは配列の左半分にある必要があります。中央の要素がそのインデックス以下の場合、欠落している要素は配列の右半分にある必要があります。

これは、変更された二分探索メソッドのコード実装です -

この方法の時間計算量も O(log n) であり、これは二分探索法と同じです。

この方法は線形検索方法より効率的であり、配列をソートする必要があります。

このブログでは、配列から最小の欠損値を見つける 4 つの方法について説明しました。これらは、単純法、二分探索法、線形探索法、および修正二分探索法です。

以上が最小の欠損値を見つけるための JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。