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

問題
1. 原文
2. 内容
方針
解答
1. 解答1
補足・参考・感想

問題

原文

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

#クラスを定義
class Solution:
    #関数を定義。配列numsはintの整数を持つリスト、変数targetはint、返り値はint
    def searchInsert(self, nums: List[int], target: int) -> int:
        #targetがnumsに含まれている場合
        if target in nums:
            #targetの要素番号を返す
            return nums.index(target)
        #targetがnumsに含まれていない場合
        else:
            #numsの要素数だけ繰り返し処理
            for i in range(len(nums)):
                #numsのi番目の要素がtargetよりも大きい場合
                if nums[i] > target:
                    #iの値を返す
                    return i
                    #終了
                    exit()
            #numsの中にtargetよりも大きい要素がなかった場合はnumsの要素数(一番最後に追加すべきという解答)を返す
            return len(nums)

#クラスを定義

class Solution:

#関数を定義。配列numsはintの整数を持つリスト、変数targetはint、返り値はint

def searchInsert(self, nums: List[int], target: int) -> int:

#targetがnumsに含まれている場合

if target in nums:

#targetの要素番号を返す

return nums.index(target)

#targetがnumsに含まれていない場合

else:

#numsの要素数だけ繰り返し処理

for i in range(len(nums)):

#numsのi番目の要素がtargetよりも大きい場合

if nums[i] > target:

#iの値を返す

return i

#終了

exit()

#numsの中にtargetよりも大きい要素がなかった場合はnumsの要素数(一番最後に追加すべきという解答)を返す

return len(nums)

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

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

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

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

#クラスを定義
class Solution:
    #関数を定義。numsはintの要素を持つリスト、targetはint、返り値はint
    def searchInsert(self, nums: List[int], target: int) -> int:
        #変数leftに0を代入(探索範囲内で一番小さい左端の要素のインデックス)
        left = 0
        #変数rightに配列numsの要素数から1を引いた値を代入(探索範囲内で一番大きい右端の要素のインデックス)
        right = len(nums)-1
        #変数rightが変数left以上である限り繰り返し処理(探索範囲が残っている限り続ける)
        while left <= right:
            #変数middleに変数leftと変数rightを合わせて2で割った数を代入(リストの真ん中の要素のインデックス)
            middle = (left + right) // 2
            #配列numsの真ん中の要素が変数targetよりも小さい場合
            if nums[middle] < target:
                #変数leftに変数middleに1を加えた数を代入。(左端のインデックスを真ん中より1つ右に変えて探索範囲を右半分に狭める)
                left = middle + 1
            #配列numsの真ん中の値が変数targetよりも大きい場合
            elif nums[middle] > target:
                #変数rightに変数middleから1を引いた数を代入。(右端のインデックスを真ん中より1つ左に変えて、探索範囲を左半分に狭める)
                right = middle - 1
            #上記に当てはまらない(真ん中の要素が変数targetと一致した)場合
            else:
                #変数middleを返す
                return middle
        #変数targetがどの要素よりも大きい(変数leftと変数rightの値が狭まりきって大小関係が変化)した場合は、変数right+1(一番最後のインデックス)を返す
        return right + 1

#クラスを定義

class Solution:

#関数を定義。numsはintの要素を持つリスト、targetはint、返り値はint

def searchInsert(self, nums: List[int], target: int) -> int:

#変数leftに0を代入(探索範囲内で一番小さい左端の要素のインデックス)

left = 0

#変数rightに配列numsの要素数から1を引いた値を代入(探索範囲内で一番大きい右端の要素のインデックス)

right = len(nums)-1

#変数rightが変数left以上である限り繰り返し処理(探索範囲が残っている限り続ける)

while left <= right:

#変数middleに変数leftと変数rightを合わせて2で割った数を代入(リストの真ん中の要素のインデックス)

middle = (left + right) // 2

#配列numsの真ん中の要素が変数targetよりも小さい場合

if nums[middle] < target:

#変数leftに変数middleに1を加えた数を代入。(左端のインデックスを真ん中より1つ右に変えて探索範囲を右半分に狭める)

left = middle + 1

#配列numsの真ん中の値が変数targetよりも大きい場合

elif nums[middle] > target:

#変数rightに変数middleから1を引いた数を代入。(右端のインデックスを真ん中より1つ左に変えて、探索範囲を左半分に狭める)

right = middle - 1

#上記に当てはまらない(真ん中の要素が変数targetと一致した)場合

else:

#変数middleを返す

return middle

#変数targetがどの要素よりも大きい(変数leftと変数rightの値が狭まりきって大小関係が変化)した場合は、変数right+1(一番最後のインデックス)を返す

return right + 1

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

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

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

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

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

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

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

補足・参考・感想

前：27.Remove Element

次：58. Length of Last Word

LeetCode 解答・解説記事一覧