ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」

次回
まだ

Twitterやってます。

問題

153. Find Minimum in Rotated Sorted Array
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、昇順にソートされた配列を，あらかじめ知らないピボットで回転させたとします。（[0,1,2,4,5,6,7]が[4,5,6,7,0,1,2]になるといったような例を思い浮かべていただけると分かりやすいかもしれません。）

そのリストの中から最小の要素を探します。

なお、配列の中に重複した要素はないと考えてよい。

Example 1:

Input: [3,4,5,1,2]
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

解法

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low,high = 0,len(nums)-1
        while low < high:
            mid = (high+low)//2
            if nums[mid] > nums[high]:
                low = mid + 1
            else:
                high = mid
        return nums[low]
# Runtime: 36 ms, faster than 92.74% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
# Memory Usage: 13.9 MB, less than 83.16% of Python3 online submissions for Find Minimum in Rotated Sorted Array.

ソートされたリストを順番を保ったまま開始と終点を入れ替えた場合、最も小さい要素を毎回返すようなアルゴリズム、ということですね。
二分探索(O(logn))が適当なアルゴリズムかと思うので、そのまま書いたら良い感じのスピードが出ました。
最近典型的なアルゴリズムの計算量について勉強しなおしているので、できるだけ適当なアルゴリズムを選択できるようになっていきたいです。
数弱なので精進せねば、という感じですね。

それにしてもこの問題二分探索の説明をするには良いですね・・・
線形探索では時間切れになるので、そういったところに目を向けるには非常に良いのでは？
さすがの問題のチョイスだと思いました。

では今回はここまで。
お疲れ様でした。