スポンサーリンク

【LeetCode】35. Search Insert Position 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約3分で読めます。

問題

原文

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

内容

全要素が異なる、ソートされた配列と目標の値(target)が与えられます。targetが配列内にあれば、その要素番号を返してください。targetが配列内になければ、昇順で入れられた場合に入るべき位置の要素番号を返してください。

 

※正しくない可能性があります。

 

方針

・計算量がO(log(n))の解法が指定されているので、二分探索を用います。

解答

解答1

変数targetの値が配列内に含まれていればその要素を返します。

含まれていなければ、配列numsを全探索し、昇順で並べられた時に入るべき位置の要素番号を返しています。

これは、実行時の計算量がO(n)であるため、問題の指定に従っていません。

O(log(n))の解法が指定されています。Discussなどを見ていると、二分探索を書いている方が多いようでした。後日そちらにも挑戦したいと思います。

Discussも参考にしつつ二分探索で解いてみました。

一番小さい数(リスト内の左端)、一番大きい数(リスト内の右端)、真ん中の数(リスト内の中央)の3つのインデックスを持っておき、

探している値が真ん中の数よりも大きければ、左端のインデックスを真ん中より1つ右に、探している値が真ん中の数よりも小さければ、右端のインデックスを真ん中より1つ左に変えて再度探索します。

これを繰り返すことで、解法1よりも早く解答することができます。

leftとrightの値はどんどん近づいていくはずで、もしleft<=rightの大小関係が変化した(探索範囲内に探している値がなかった)場合は一番後ろに追加する必要があるのでright+1を返しています。

探索範囲が毎回半分になるので計算量がO(log(n))になります。

二分探索は最初にリストを昇順に並べ替えておく必要がありますが、入力された時点で既に昇順になっているので今回は必要ないと思います。

補足・参考・感想

 

前:27.Remove Element

次:58. Length of Last Word

LeetCode 解答・解説記事一覧

コメント