どーも！
たかぽんです！
今回は三日目！
明日続けばなんとか三日坊主は避けられそうです...w
今回はSearch Insert Positionを解きました。
では簡単に説明だけ書いておきます...!
Search Insert Position
さて、今回は以下の問題です。
内容としては、リストの中にソートされた数字が入っていて、targetの数値がリストのどの位置にくるのか？を探してあげる問題です。
例えば...
[1,2,3,4,5]というリストに対して、6がtargetの場合... [1,2,3,4,5,6]となり、リストの値全てより大きいのでリスト末尾になります。そのため、そのindexである5を返せばOKです。間にくる場合ももちろんあり...
[1,2,4,6,8,9]というリストに対して、5がtargetの場合... [1,2,4,5,6,8,9]となり、3を返せばOKです。また、すでにリストの中に同じ数値がある場合...
その同じ数値の一番先頭に追加すればOKです。
[1,2,3,4,5]に対して、3がtargetなら.... [1,2,3,3,4,5]となるため、2を返せばOKです。(3ではダメです)基本的には上記のような形になります。
アルゴリズム
では、簡単にアルゴリズムを検討しておきます。
まず、すでにtargetとなる数値がリストに存在する場合、その一致した値があったインデックスを返せば大丈夫です。
これは、リストの若い順番から捜査し、一番左にあるインデックスの値が検索され、その部分にtargetを挿入すれば大丈夫なためです。
これでtargetが含まれる場合はOKです。
次に、targetがどの要素よりも大きい場合、小さい場合です。
この場合、それぞれリストの一番最後か、一番最初になります。
リストの最後は、リストの長さのカウントがそのまま末尾に一つ新しく追加した値になります。（リストのindexは0始まりで、長さのカウントは1から始まるため)
そのため、[1,2,3]の末尾に追加するためには0,1,2,3で、インデックスが3の場所に追加すればいいわけですね。
逆にリストの最初は0番目のインデックスとして追加すればOKです。
これで、targetがリストに含まれるorリストの全ての値より大きいor小さい場合は網羅しました。
最後にリストの中にくる場合です。
この場合、numsの中身を一つづつ見ていき、targetが大きい間は無視、numsの中身がtargetよりも大きくなった瞬間、そのindexを返せばいいはずです。
たとえば...
[1,3,5,7,9]に4を入れる場合...1,4で比較するとtargetが大きいので次へ。index = 0
3,4で比較するとtargetが大きいので次へ。index = 1
5,4で比較するとtargetが小さいので、この時のindex = 2を返せばOKですね。
上記まで書けば一通りうまく動くはずです。
より速度重視でいくならば...
例えば最後の比較部分で、一番初めにリストの真ん中辺りの値と比較をすれば、大小でそれより後ろか、前の要素だけに選択肢が絞られるので、今度は前半部分のさらに真ん中、または後半部分のさらに真ん中...といった形で探すとより効率はよくなりそうな気がします...!
そういった効率については探索アルゴリズムで、線形探索（今回行った最初っから比較していくもの）や、二分探索（さっき説明した、大小のグループに分けてどちらかを繰り返し判断していくもの)等を調べてもらえればと思います...!
提出したコード
以下、僕が実際に提出したコードを記載しておきます。
意外と早かったらしく、嬉しいです...!
Runtime: 44 ms, faster than 91.93% of Python3 online submissions for Search Insert Position.
Memory Usage: 15.1 MB, less than 55.41% of Python3 online submissions for Search Insert Position.class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# targetが含まれる場合
if target in nums :
return nums.index(target)
# targetがどの要素より大きい場合
if target > max(nums) :
return len(nums)
# targetがどの要素より小さい場合
if target < min(nums) :
return 0
# リストの中間に入る場合
for index,num in enumerate(nums):
if target < num:
return index
