ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day85 「6. ZigZag Conversion」

次回
ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」

Twitterやってます。

問題

33. Search in Rotated Sorted Array

難易度はMedium。
問題としては、昇順にソートされた配列を，あらかじめ知らないピボットで回転させたとします（[0,1,2,4,5,6,7]が[4,5,6,7,0,1,2]になるかもしれません。）
(例えば，[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になるかもしれません。)
検索対象の値が与えられます。配列の中に見つかった場合はそのインデックスを返し、そうでない場合は-1を返します。
配列の中に重複したものが存在しないと仮定しても構いません。
なお、アルゴリズムの実行時の複雑さは，O(log n)のオーダーでなければなりません。

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

解法

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if nums.count(target) == 0:
            return -1
        else:
            ans = nums.index(target)
        return ans
# Runtime: 36 ms, faster than 92.59% of Python3 online submissions for Search in Rotated Sorted Array.
# Memory Usage: 14 MB, less than 61.16% of Python3 online submissions for Search in Rotated Sorted Array.

仮にcountが0ならば-1を返し、そうでない場合にindexを返します。

・・・
書くことがなぁい！！！

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