arrays - 各要素が前の要素よりも 1 つ多いまたは 1 つ少ない配列内の要素を検索します

Question

array を指定すると、各要素はその前の要素よりも 1 つ多いか 1 つ少なくなります。その中の要素を見つけます。(O(n) アプローチよりも優れています)

これに対する解決策はありますが、それが正しい解決策であるかどうかを正式に伝える方法はありません。

n を見つけなければならないとしましょう。

• 指定されたインデックスから、n までの距離を見つけます。d = |a[0] - n|
• 目的の要素は、少なくともd要素が離れており、d要素をジャンプします
• d上記を= 0まで繰り返す

Answer 1

ここでは前処理が役立ちます。O（n）時間の複雑さで配列の最小要素と最大要素を見つけます。クエリ対象の要素が配列の最小値と最大値の間にある場合、その要素は配列に存在します。それ以外の場合、その要素はその配列に存在しません。したがって、クエリには O(1) 時間がかかります。その配列が複数回クエリされた場合、償却された時間の複雑さは O(n) よりも小さくなります。