【LeetCode】153. Find Minimum in Rotated Sorted Array 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python, 二分探索
2. 解答2:
メモ・参考・感想

問題

原文

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.

[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

1
2
3

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

1
2
3

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

1
2
3

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length

1 <= n <= 5000

-5000 <= nums[i] <= 5000

All the integers of nums are unique.

nums is sorted and rotated between 1 and n times.

内容

長さnの昇順に並べ替えられた配列は1からn回回転します。

例えば、配列nums = [0,1,2,4,5,6,7]はこのようになります。

・[4,5,6,7,0,1,2]　4回回転した場合

・[0,1,2,4,5,6,7]　7回回転した場合

回転は[a[0],a[1], … , a[n-1]]が1回回転すると[a[n-1], a[n], … , a[n-2]]になります。

※つまり、一番後ろが一番前にくる

ソートされた配列numsの要素に重複はありません。配列の最小要素を返してください。

計算量O(log(n))で書かなければなりません。

※正しくない可能性があります。

解答

解答1：Python, 二分探索

"""
leftを最小の要素を指すインデックスに保ち二分探索を行う。
二分探索後、leftを戻り値とする
"""

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        #左インデックスが右インデックス未満である限り続ける
        while left < right:
            #真ん中のインデックスを取得
            middle = (left + right) // 2
            #中央の要素がnum[right]より大きい場合　※nums[right]はnumsの右端とは限らない
            if nums[middle] > nums[right]:
                #leftをmiddelの右へ移動　
                #※nums[3,4,5,1,2]の場合、nums[middle]=5で、nums[right]=2より大きいのでleft=3、つまりnums[left]=1となり、leftが最小値のインデックスとなる
                left = middle + 1
            #中央の要素がnum[right]以下の場合
            #※nums[3,4,5,1,2]の場合、right=3,nums[right]=1で、leftとrightは一致する
            else:
                right = middle
        return nums[left]

"""

leftを最小の要素を指すインデックスに保ち二分探索を行う。

二分探索後、leftを戻り値とする

"""

class Solution:

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

left = 0

right = len(nums) - 1

#左インデックスが右インデックス未満である限り続ける

while left < right:

#真ん中のインデックスを取得

middle = (left + right) // 2

#中央の要素がnum[right]より大きい場合　※nums[right]はnumsの右端とは限らない

if nums[middle] > nums[right]:

#leftをmiddelの右へ移動　

#※nums[3,4,5,1,2]の場合、nums[middle]=5で、nums[right]=2より大きいのでleft=3、つまりnums[left]=1となり、leftが最小値のインデックスとなる

left = middle + 1

#中央の要素がnum[right]以下の場合

#※nums[3,4,5,1,2]の場合、right=3,nums[right]=1で、leftとrightは一致する

else:

right = middle

return nums[left]

・二分探索を使用する

・leftを最小値を指すインデックスに保つことを考える

・中央の要素が、rightが指す要素より大きい場合、leftをmiddleの1つ右にする。

※繰り返すと最大値に近づいていき、最大値を経て最小値になる

・中央の要素がrightが指す要素よりも小さい場合、rightにmiddleを代入する。

leftとrightの範囲を狭めながら最小値を挟み込んでいくイメージ

解答2:

メモ・参考・感想

・感想

二分探索ってこんな風にも使えるのかと思った。

昇順のリストで小さい方の要素を前から後ろに回転する場合はrightを使って最大値を、降順のリストで小さい方の要素を後ろから前に回転する場合はleftを使ってこれも最大値を取ったりできるのだろうか。

前：74. Search a 2D Matrix

次：844. Backspace String Compare

LeetCode 解答・解説記事一覧