NeetCodeのSolutionを書いていく

#

Find Minimum In Rotated Sorted Array

#

問題

#

長さnの配列が与えられます。 もともとは昇順ソートされていたものです。 1~n回のローテーションがされています。 例えば[1,2,3,4,5,6]は4回ローテーションすると[3,4,5,6,1,2]、6回ローテーションすると[1,2,3,4,5,6]になります。 4回ローテーションすると最後の4つの要素が最初に移動します。6回ローテーションすると最初と同じになります。 numsの要素はユニークとする時の最小の要素を返しなさい。 計算量がO(n)のアルゴリズムができるのは当然です。O(logn)出できますか？

制約

#

• numsの長さは1以上1000以下
• numsの要素は-1000以上1000以下

計算量：O(logn) メモリ：O(1)

例

#

Input: nums = [3,4,5,6,1,2] Output: 1

Input: nums = [4,5,0,1,2,3] Output: 0

Input: nums = [4,5,6,7] Output: 4

メモ

#

もともとソートされている配列なので、ローテーションするとソートされた２つの配列になる。 ソートの切れ目に最小値がある。 配列の左端l右端r真ん中mを考えた時

nums[l] < nums[m] であれば左の配列はソート済み、 この時nums[m] < nums[r]であれば右の配列もソート済みなので最小値はnums[0] そうでない場合は、mrの間に最小値がある。nums[m]とnums[r]の値から最小値を保持しておく l=m, m=(l+r)//2として繰り返す l==mとなったら処理終了 そうでない場合は左の配列はソートされていない(ソートの切れ目がある)のでlmの間に最小値がある nums[l]とnums[m]の最小値を保持しておく r = m, m=(l+r)//2として繰り返す r == m となったら処理終了

徐々に探索範囲を半分にするのでO(logn)最小値を保持するためのメモリがO(1)

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1
        m = (l + r) // 2

        while True:
            mv = min(nums[m], nums[r])
            if nums[l] < nums[m]:
                if nums[m] < nums[r]:
                    return nums[0]
                l = m
            else:
                r = m

            m = (l + r) // 2
            if l == m or r == m:
                return mv